C++ dp solution easy to understand one time pass


  • 0
    Q
    class Solution {
    public:
        int wiggleMaxLength(vector<int>& nums) {
            vector<vector<int>> res(nums.size(),vector<int>(2,0));
            if(nums.size() <= 1)
                return nums.size();
            res[0][0] = 1;
            res[0][1] = 1;
            int ret = 1;
            for(int i=1;i<nums.size();i++){
                for(int j=i-1;j>=0;j--){
                    if(nums[i] > nums[j]){
                        res[i][1] = max(res[i][1],res[j][0]+1);            
                    }
                    else if(nums[i] < nums[j]){
                        res[i][0] = max(res[i][0],res[j][1]+1); 
                    }
                }
                ret = max(ret,max(res[i][0],res[i][1]));
            }
            return ret;
        }
    };
    

Log in to reply
 

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