Longest choppy zigzag inside a price series
A "zigzag" subsequence has strictly alternating moves: up, then down, then up, and so on (no two consecutive moves in the same direction, and no flat moves). Given prices, find the length of the longest zigzag subsequence.
prices = [1, 7, 4, 9, 2, 5]
-> 6 # every step already alternates: +, -, +, -, +
Return the length of the longest alternating subsequence in O(n) time.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.