We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
A wiggle sequence is one where the differences between successive numbers strictly alternate between positive and negative. Given an integer array nums, return the length of the longest wiggle subsequence obtainable by deleting some elements (keeping order).
A medium dynamic programming problem, graded against 7 test cases (5 of them hidden).
Overlapping subproblems solved once and reused - the pattern candidates fear most.
Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.
More Dynamic Programming problems →Greedy up/down tracking. Maintain `up` and `down`, the lengths of the longest wiggle subsequences ending with a rise or a fall. On each rise set `up = down + 1`; on each fall set `down = up + 1`. The answer is `max(up, down)`.
Time: O(n). Space: O(1).
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
Read off this problem's own test suite, so these are the cases a submission actually has to survive.
These apply to the pattern as a whole, not just this problem.