Untitled
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