# 376. Wiggle Subsequence

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, `[1,7,4,9,2,5]` is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, `[1,4,7,2,5]` and `[1,7,4,5,5]` are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

``````**Input:** [1,7,4,9,2,5]
**Output:** 6
The entire sequence is a wiggle sequence.

**Input:** [1,17,5,10,13,15,10,5,16,8]
**Output:** 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

**Input:** [1,2,3,4,5,6,7,8,9]
**Output:** 2
``````

Can you do it in O( n ) time?

Credits:
Special thanks to @agave and @StefanPochmann for adding this problem and creating all test cases.

``````class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.empty()) return 0;
vector<int> p(nums.size(), 1);
vector<int> q(nums.size(), 1);
for (int i = 1; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) p[i] = max(p[i], q[j] + 1);
else if (nums[i] < nums[j]) q[i] = max(q[i], p[j] + 1);
}
}
return max(p.back(), q.back());
}
};
``````

``````class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int p = 1, q = 1, n = nums.size();
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i - 1]) p = q + 1;
else if (nums[i] < nums[i - 1]) q = p + 1;
}
return min(n, max(p, q));
}
};
``````

Wiggle Sort

Wiggle Sort II

https://discuss.leetcode.com/topic/51893/two-solutions-one-is-dp-the-other-is-greedy

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏 （欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～） ×

Help us with donation  