376. Wiggle Subsequence

I was trapped in finding a DP solution that dp[i] means the longest wiggle subsequence so far at index i. However, I then realized two things: 1. The wiggle subsequence is not necessary to be consecutive; 2. [2,1] is a wiggle and [1,2] is a wiggle too. So I can’t solve it by something like Kadane’s algorithm. I followed the top rated solution which uses two dp arrays and runs at O(n^2) because subsequence is not required to be consecutive.

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