@llkk Here I tried to prove greedy solution: check if it helps.

Suppose the given input sequence is `[a0, a1, a2, ... , ai, ... , an]`

Say our greedy solution will always pick `a0`

into our final answer (according to algorithm given). And what we treat it, as an *up element* or a *down element*, is determined by comparing it with `a1`

.

Let's assume `a0 < a1`

, so we are treating `a0`

as a *down element*.

Now consider there is an optimal solution (opt) sequence starting with `ai (0 <= i <= n)`

.

If `ai`

is considered as an *up element* by opt, then we must have `a0 >= ai`

, otherwise by appending `a0`

we can have a better solution sequence. The same idea when `ai`

is treated as *down element* by opt.

**Thus, we can always replace ai with a0 so that we have another solution which is still optimal.** Denote the new optimal solution with opt'.

In opt`, if `a0`

is treated as *up element*, because `a1`

is larger than `a0`

according to our assumption, by replacing `aj`

, which is the second element in opt', with `a1`

in opt' we can have another optimal solution opt''. Because we are picking both `a0`

and `a1`

and opt'' is also picking them, this will cause induction.

if `a0`

is treated as *down element*, which is the same as our solution, we can delete `a0`

from input and start running both our algorithm and opt' from `a1`

instead. This will also cause induction.

Omit the details of proving induction...