Straightforward Python solution with clear explanation

• 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
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.