DFS with memories .very easy to understand!!!


  • 0
    class Solution {
    public:
        int helper(vector<int>& nums,int index,int state,int num,vector<vector<vector<int>>>&vis){//2:nextbiger  1:nextlittle 0:firstnum
            if(index==nums.size())return 0;
            if(vis[num][index][state]!=-1)return vis[num][index][state];
            int maxlen=0;
            for(int i=index;i<nums.size();i++){
                if(state==0){
                    maxlen=max(maxlen,1+helper(nums,i+1,1,nums[i],vis));
                    maxlen=max(maxlen,1+helper(nums,i+1,2,nums[i],vis));
                }else if(state==1){
                    if(nums[i]<num)maxlen=max(maxlen,1+helper(nums,i+1,2,nums[i],vis));
                }else if(state==2){
                    if(nums[i]>num)maxlen=max(maxlen,1+helper(nums,i+1,1,nums[i],vis));
                }
            }
            vis[num][index][state]=maxlen;
            return maxlen;
        }
        int wiggleMaxLength(vector<int>& nums) {
            if(nums.empty())return 0;
            int maxnum=nums[0];
            for(int i=1;i<nums.size();i++){
                maxnum=max(maxnum,nums[i]);
            }
            vector<vector<vector<int>>>vis(maxnum+1,vector<vector<int>>(nums.size(),vector<int>(3,-1)));
            return helper(nums,0,0,0,vis);  
        }
    };
    

Log in to reply
 

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