0376. Wiggle Subsequence¶
Given an integer array nums, return the length of the longest wiggle sequence**.
A wiggle sequence is a sequence where 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.
A subsequence is obtained by deleting some elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.
Example 1:
Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence.
Example 2:
Input: nums = [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Example 3:
Input: nums = [1,2,3,4,5,6,7,8,9]
Output: 2
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1000
Follow up: Could you solve this in O(n) time?
Analysis¶
The brute force solution is using "choose or not" method to check for each element from the array, and it takes O(n) for each result validation (check if is indeed waggle), and the total time complexity is O(n! \times n) It will result TLE.
Dynamic Programming: Another approach is using two arrays to record the current status' longest subsequence count (with the last element being nums[i]). For each point, we could choose either to append the previous "raising" subsequence or "falling" subsequence — thus we need two arrays. The time complexity for this approach is O(n^2), and the space complexity is O(2 \times n).
Dynmaic Programming Improved: If we think carefully, there are some correlation between our two arrays. If we mark one array as up[i] and another one as down[i], we can find that if nums[i] > nums[i-1] (going up), the previous one must be going down, and we will have the maximum value from down[i - 1], since down[i - 1] >= down[i - 2] … >= down[0]. Same logic applies to nums[i] < nums[i - 1]. Using this method we don't need to iterate through the nums[i] twice, but just a linear scan should be able to solve this problem. To further improve, since we are only interested in the previous down or up, we don't need to store all the result from down[0] … down[i-1], so we can minimize these arrays into two variables. Time complexity will be O(n) and space is O(1).
Code: brute force¶
class Solution {
public:
int dfs(vector<int>& a, int idx, bool status) {
int cnt = 0;
// start checking from current index + 1
for (int i = idx + 1; i < a.size(); ++i) {
// a[prev] < a[i]
if ((status && a[i] > a[idx]) || (
// a[prev] > a[i]
!status && a[i] < a[idx])) {
cnt = max(cnt, 1 + dfs(a, i, !status)); // each iteration will change the direction
}
}
return cnt;
}
int wiggleMaxLength(vector<int>& a) {
if (a.size() < 2) return a.size();
return 1 + max(dfs(a, 0, false), dfs(a, 0, true));
}
};
Code: DP with two arrays¶
class Solution {
public:
int wiggleMaxLength(vector<int>& a) {
int n = a.size();
if (n < 2) return n;
vector<int> up(n), down(n);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (a[i] < a[j]) { // now: up, prev: down
down[i] = max(down[i], up[j] + 1);
} else if (a[i] > a[j]) { // now: down, prev: up
up[i] = max(up[i], down[j] + 1);
}
}
}
return max(up.back(), down.back()) + 1;
}
};
Code: DP with two variables¶
class Solution {
public:
int wiggleMaxLength(vector<int>& a) {
int n = a.size();
if (n < 2) return n;
int up = 1, down = 1;
for (int i = 1; i < n; ++i) {
if (a[i] < a[i - 1]) // now: up, prev: down
/*
up = max(up, down + 1);
we can acutally ignore up, since prev has to be down and if we don't choose, our down variable isn't changed
*/
up = down + 1;
else if (a[i] > a[i - 1])
/*
down = max(down, up + 1);
same logic here
*/
down = up + 1;
}
return max(up, down);
}
};