k217. 11240 - Antimonotonicity

<<回主頁

解題想法

這題好像是 UVa 那裏搬來的，一開始覺得是 LIS 的變形，改成 zig-zag 的 LIS，但後來發現不是，解題想法是透過 greedy 的想法。

假設我們前面選了一個低點，現在要找比他大的，找到大的當然拿了開心收場，找到低的怎麼辦呢? 我們發現我們改成拿後面更低的更好，這不會影響到前一項的性質，因為前面既然就是要找低點，那我拿個更低的也一定符合；反之找到大的就先直接拿了，接著開始找小的，沿用前面的想法就行，實作的話就是維護現在的最大或最小值，然後用一個變數去記目前要找大還是小。

最後這題就掃過去就好了，每筆時間複雜度

$O(n)$。