Straightforward Python solution with clear explanation

  • 0

    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
                up = up
                down = down
        return max(up, down)+1

Log in to reply

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