Recently I came across a task from Polish Informatics Olympiad called "Fence" and I can't solve it.
The first input line contains integer number
1 <= n <= 200 000) and the second line contains
n numbers (each is not less than
1 and not greater than
10^6). You have to delete some numbers so that the sum of the remaining ones is as large as possible and the their values have to increase and decrease. I mean, if
A is a set of remaining numbers and
i-th number from set then
a1 < a2 > a3 < a4 > a5 < a6 etc. or
a1 > a2 < a3 > a4 < a5 > a6 etc.
From range of
n values, it seems that the complexity of solution would be similar to
O(n log n), but I'm not sure about that. I'd be grateful if someone told me the solution.
7 5 4 6 6 5