Untitled

 avatar
unknown
plain_text
a year ago
917 B
8
Indexable
class Solution {
public:
    int dp[10001][3];
    int signChk(int &a, int &b){
        int neg = b-a;
        if(neg<0) return 1;
        else return 2;
    }
    int f(int ind, int prev, int n, vector<int>&nums){
        if(ind==n) return 0;
        if(dp[ind][prev]!=-1) return dp[ind][prev];
        int notPick = f(ind+1, prev, n, nums);
        int pick = 0;
        if(prev==0 || prev != signChk(nums[ind], nums[ind-1])){
            pick = 1 + f(ind+1, signChk(nums[ind], nums[ind-1]), n, nums);
        }
        return dp[ind][prev] = max(pick, notPick);
    }
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if(n<=1) return 1;
        memset(dp, -1, sizeof dp);
        /*finally tle not WA, let's go*/
        int i =1;
        while(i<n && nums[i] == nums[i-1]) i++;
        if(i==n) return 1;
        else return 1+f(i, 0, n, nums);
    }
};
Editor is loading...
Leave a Comment