ZigZag sequence without dynamic programming
Your simple algorithm is correct.

In fact, you have proved the correctness of your algorithm basically since your algorithm is, as you have written, based on finding all the local maximum and minimum of the original sequence. The simple mathematical reason is that for each zigzag, i.e., $a[i]&lt;a[i+1]&gt;a[i+2]$ or $a[i]&gt;a[i+1]&lt;a[i+2]$, there must exist a local maximum or a local minimum respectively. 

A more rigorous and rather tedious proof is needed to convince all of us that there is no off-by-one error in your program. However, I will skip it since it is routine and not enlightening at all.