Wiggle Subsequence
Medium · Online assessment (OA) · Phone screen · Onsite · Full-time
Find the longest subsequence where differences between successive numbers strictly alternate between positive and negative. I tracked the length of sequences ending on an up or down move. Each time the direction changed, I extended the appropriate counter. Greedy approach works in O(n) without needing full DP.
