Know This Problem?#13112

Know This Problem? (Editorial)

Call the non-decreasing subsequence and the non-increasing one , and process the elements from left to right. Whether the rest of the array can still be placed depends only on the last element of and the last element of . A new element can join if it is at least the last element of , and join if it is at most the last element of , so a smaller last element of and a larger last element of are never worse. An empty acts as , and an empty as .

Two numbers are enough. After processing h_i, one of the two last elements is h_i itself. So we keep only

Initially u = +\infty and d = -\infty. Let p = h_i and x = h_{i+1}.

The new is the maximum of its candidates and the new is the minimum of its candidates ("impossible" if there are none). The answer is YES if and only if or is possible at the end. This is time, and the array does not even have to be stored.

All comparisons are non-strict, because equal values are allowed in both subsequences: a solution for strictly monotone subsequences fails. Keep "impossible" separate from "empty" and from real values: 10^9 is a valid value, so it cannot serve as .

Remark: finding a split. Remember for every which transition gave and , and walk back from i = n. An equivalent greedy: if h_i fits only one subsequence, put it there; if it fits both, look at the next value w \ne h_i and put h_i into if w < h_i, and into otherwise. Looking only at h_{i+1} is not enough, because a long run of equal values may come before .