Wiggle Subsequence

Problem

A wiggle sequence has alternating positive/negative differences. Return the length of the longest wiggle subsequence (in order, not necessarily contiguous).

Constraints

• 1 ≤ n ≤ 1000

Approach — Dynamic Programming

This is a Dynamic Programming problem. The idea: break the problem into overlapping subproblems and build the answer up, caching results so nothing is recomputed. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) to O(n²) time.

Solution code

Python

class Solution:
    def wiggleMaxLength(self, nums):
        if len(nums) < 2:
            return len(nums)
        up = down = 1
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                up = down + 1
            elif nums[i] < nums[i - 1]:
                down = up + 1
        return max(up, down)

Java

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) return nums.length;
        int up = 1, down = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i-1]) up = down + 1;
            else if (nums[i] < nums[i-1]) down = up + 1;
        }
        return Math.max(up, down);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.