Once you see this problem correctly it's quite simple to code. But it took me a while to see it. There are several explanations using dynamic programming and they are correct and equivalent to this solution. However it took me a while to understand how to build the subproblems.
Let's consider this. You need to build a sequence of the sign of differences. To get a difference you need two numbers. In the sequence [1, 2, 1] you have two differences: [+, -]. So, to build the subproblems in dynamic programming you don't need to think about individual numbers but in pairs to form a difference.
For every single pair there are three options:
- it's + and can be added to a previous sequence ending with a -
- it's - and can be added to a previous sequence ending with a +
- there is no difference, so you can't add it
Of course, the result should be the maximum sequence, ending in a + or -. And as we are required to return the length, not the number of differences, we need to add an extra +1.
def wiggleMaxLength(nums): if not nums: return 0 up = 0 down = 0 for i in range(1, len(nums)): if nums[i] > nums[i-1]: up = down+1 down = down elif nums[i] < nums[i-1]: up = up down = up+1 else: up = up down = down return max(up, down)+1