Codeforces #27 C Unordered Sequence

題意﹕給了N個數A1, A2... AN，一個有序數列是指數列是單調遞升或者遞降，求A之中最短的非有序子序列。可以無解。

看了也想了很久，誤解以為找了這個最短的非有序子序列之後剩下的序列必須是有序的…但其實不是，題目實實在在的只想你求一條最短的非有序子序列。

發現之後此題巨簡單﹕若有解，則該序列的長度永遠等於3。即找i, j, k使得 i < j < k 並且 Ai < Aj, Aj > Ak 或 Ai > Aj, Aj < Ak。

做法巨簡單﹕O(N)求 LeftMin[i], LeftMax[i], RightMin[i], RightMax[i]，分別是指A[1..(i-1)]和A[i+1..N]最小最大的位置。

又一次腦便秘，下次看題要看清。