# O(n) solution c++ code

• This is basically a variation of 'longest increasing subsequence' problem. Refer to:
https://en.wikipedia.org/wiki/Longest_increasing_subsequence

The solution maintains 2 auxiliary arrays, s[i] stores the longest wiggle length up to index i; p[i] stores the wiggle link (precedent index link. it is not needed but I will just put it here as a pattern of solving similar problems.).

``````int wiggleMaxLength(vector<int>& nums) {

int len = nums.size();
if (len < 2)
return len ? 1 : 0;

vector<int> s(len, 0);
vector<int> p(len, 0);

s[0] = 1; s[1] = nums[0] == nums[1] ? 1 : 2;
p[0] = -1; p[1] = nums[0] == nums[1] ? -1 : 0;
for (int i = 2; i < len; i++){

if ((nums[i] > nums[i - 1] && nums[i - 1] < nums[p[i - 1]]
|| nums[i] < nums[i - 1] && nums[i - 1] > nums[p[i - 1]]))
s[i] = s[i - 1] + 1, p[i] = i - 1;
else
s[i] = s[i - 1], p[i] = p[i - 1];
}

return s[len - 1];
}``````

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