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:  };  

280. Wiggle Sort

The final sorted array must follow:
1. If i is odd, nums[i] >= nums[i-1]
2. If i is even, nums[i] <= nums[i-1]
The invariance is that nums[i-1] has been wiggle sorted. If i is odd, nums[i-1] <= nums[i-2]. So if nums[i] < nums[i-1], it must satisfy nums[i] < nums[i-2], so swapping nums[i] and nums[i-1] doesn’t break the invariance, and especially, after swapping, the invariance is kept till nums[i]. Same to the case of even i.

1:  class Solution {  
2:  public:  
3:    void wiggleSort(vector<int>& nums) {  
4:      for (int i = 1; i < nums.size(); i++) {  
5:        if (((i & 1) && nums[i] < nums[i-1]) || (!(i & 1) && nums[i] > nums[i-1])) {  
6:          swap(nums[i], nums[i-1]);  
7:        }  
8:      }  
9:    }  
10:  };