Leetcode - 376 Wiggle Subsequence

Posted on | In , ,

It taked me a long time to understand the solutions in Discussion, so I decided to explain it by myself.

Solution

It’s easy to reach a O(n^2) solution. However, the follow up asks us to solve this problem in linear time. We can’t define upper[i], down[i] as the longest wiggle subsequence ends at i and is upper/lower case. When you define the state in this way, you can’t avoid to traverse back and make the time complexity O(n^2). One solution is to define upper[i], down[i] as the longest wiggle subsequence before i. This state prevent us from traversing again. But we can’t always define dp in this way because this needs the transistion equation only use the i-1 state to update state i. Why this defination works? See the following proof:
leetcode376.jpeg

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int up[1005], down[1005];
        up[0] = down[0] = 1;
        for(int i=1;i<nums.size();i++) {
            if(nums[i-1]>nums[i]) {
                down[i] = up[i-1]+1;
                up[i] = up[i-1];
            } else if(nums[i-1]<nums[i]) {
                up[i] = down[i-1]+1;
                down[i] = down[i-1];
            } else {
                down[i] = down[i-1];
                up[i] = up[i-1];
            }
        }
        return max(down[nums.size()-1], up[nums.size()-1]);
    }
};