網頁

2014年3月21日 星期五

UVa 10534 Wavio Sequence

Longest Increased/Decreased Subsequence
想法:
    替數列建LIS和LDS表,然後在從表中找出共同最大的數字。例如:
數列: 1 2 3 4 5 3 2
LIS:  0 1 2 3 4 0 0
LDS:  0 0 0 0 2 1 0
因此數字'5'的LIS為4,LDS為2,所以'5'為中心組成Wavio Sequence的長度就是min(4,2)*2+1=5。因此本題就從LIS和LDS表中找出最長的Wavio Seq長度。
    至於求LDS我是由後面往前作LIS,因此這題就是做兩次LIS,另外要注意如果用O(n^2)演算法可能會TLE。