376. Wiggle Subsequence

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast,[1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2

Follow up:
Can you do it in O(n) time?

因为是大小大小这样的形式或者小大小大这样

因此，difference will be +-+-+- or -+-+...

所以当不满足条件的时候，就是有连续++ or --出现。那么对于++保存最大位置，对于--保存最小.因此都是记录连续相同符号最开始的差值-------Greedy 

特殊处理，把第一个位置前面想象成和第一个值相同来处理 -> diff 为0。两个连续数字相同的时候不计diff，这样diff 为0只有在k，避免错误。

  public int wiggleMaxLength(int[] nums) {  
     if(nums.length < 2) return nums.length;  
     int ans = 1;  
     int diff = 0;  
     for(int i = 1; i < nums.length; i++){  
       if(nums[i] - nums[i-1] > 0 && diff <= 0){  
         ans++;  
         diff = nums[i] - nums[i-1];  
       }else if(nums[i] - nums[i-1] < 0 && diff >= 0){  
         ans++;  
         diff = nums[i] - nums[i-1];  
       }  
     }  
     return ans;  
   }  

2. dp解法
这道题可以看作是每个位置可以说大的那个位置，也可以是小的那个位置。
因此维护两个dp 一个是形成递增的长度，一个是形成递减的长度
incr[i] = max(incr[i], desc[j]+1)
desc[i] = max(desc[i], incr[j]+1)
O(n^2)

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int size=nums.size();
        if(size==0) return 0;
        vector<int> f(size, 1);
        vector<int> d(size, 1);
        for(int i=1; i<size; ++i){
            for(int j=0; j<i; ++j){
                if(nums[j]<nums[i]){
                    f[i]=max(f[i], d[j]+1);
                }
                else if(nums[j]>nums[i]){
                    d[i]=max(d[i], f[j]+1);
                }
            }
        }
        return max(d.back(), f.back());
    }
};