Another interesting DP. Lesson learnt: how you define state is crucial..

1. if DP[i] is defined as, longest wiggle(up\down) subseq AT number i, you will have O(n^2) solution

class Solution {    struct Rec    {        Rec(): mlen_dw(0), mlen_up(0){}        Rec(int ldw, int lup): mlen_dw(ldw), mlen_up(lup){}        int mlen_dw;        int mlen_up;    };public:    int wiggleMaxLength(vector
     
      & nums)     {        int n = nums.size();        if(n < 2) return n;                vector
      
        dp(n);        dp[0].mlen_up = dp[0].mlen_dw = 1;        int ret = 1;        for(int i = 1; i < n; i ++)        {            int cv = nums[i];            for(int j = i - 1; j >= max(0, ret - 2); j --)            {                if(cv > nums[j])                {                    dp[i].mlen_up = max(dp[i].mlen_up, dp[j].mlen_dw + 1);                }                else if(cv < nums[j])                                    {                    dp[i].mlen_dw = max(dp[i].mlen_dw, dp[j].mlen_up + 1);                }                ret = max(ret, max(dp[i].mlen_dw, dp[i].mlen_up));            }        }                return ret;    }};
      
     

2. if DP[i] is defined as, longest wiggle(up\down) subseq SO FAR UNTIL number i, you will have O(n) solution

class Solution {    struct Rec    {        Rec(): mlen_dw(0), mlen_up(0){}        Rec(int ldw, int lup): mlen_dw(ldw), mlen_up(lup){}        int mlen_dw;        int mlen_up;    };public:    int wiggleMaxLength(vector
     
      & nums)     {        int n = nums.size();        if(n < 2) return n;                vector
      
        dp(n);        dp[0].mlen_up = dp[0].mlen_dw = 1;        int ret = 1;        for(int i = 1; i < n; i ++)        {            int cv = nums[i];            dp[i] = dp[i - 1];            if(cv > nums[i - 1])            {                dp[i].mlen_up = max(dp[i].mlen_up, dp[i - 1].mlen_dw + 1);            }            else if(cv < nums[i - 1])                                {                dp[i].mlen_dw = max(dp[i].mlen_dw, dp[i - 1].mlen_up + 1);            }            ret = max(ret, max(dp[i].mlen_dw, dp[i].mlen_up));        }                return ret;    }};
      
     

3. And, there's always smarter solution - GREEDY!