C++ Straightforward solution. O(n)


  • 0
    S
    class Solution {
    public:
        void helper(vector<int>& nums,int start,int end,vector<int>& dp) {
            int i=0;
            bool nextflag;
            while(nums[i+1]==nums[i]&&i+1<=end) {
                i++;
            }
            if(i+1>end) {
                return ;
            }
            cout<<i<<endl;
            //false means the next one should be smaller
            //true means the next one should be bigger
            if(nums[i+1]>nums[i]) {
                nextflag=false;
            } else {
                nextflag=true;
            }
            dp[i+1]=2;i++;
            for(;i+1<=end;i++) {
                if(nextflag==false&&nums[i]>nums[i+1]||(nextflag==true&&nums[i]<nums[i+1])) {
                    dp[i+1]=dp[i]+1;
                    nextflag=(!nextflag);
                } else {
                    dp[i+1]=dp[i];
                }
            }
        }
        int wiggleMaxLength(vector<int>& nums) {
            int s=nums.size();
         //   cout<<s<<endl;
            if(s<=1) {
               // cout<<"catch"<<endl;
                return s;
            }
            vector<int> dp(s,1);
            helper(nums,0,s-1,dp);
            return dp[s-1];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.