Problem
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 one element and a sequence with two non-equal elements are trivially wiggle sequences.
- For example,
[1, 7, 4, 9, 2, 5]is a wiggle sequence because the differences(6, -3, 5, -7, 3)alternate between positive and negative. - In contrast,
[1, 4, 7, 2, 5]and[1, 7, 4, 5, 5]are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.
A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.
Given an integer array nums, return the length of the longest wiggle subsequence of nums.
Solution
Seeing finding a longest sequence, dynamic programming probably should be the first thing coming to mind.
We should have two table that keeps track of:
- The longest wiggle sequence that ends with a increasing number.
- The longest wiggle sequence that ends with a decreasing number.
Therefore, when iterating though the given array, we could first check if this nums[i] a increasing / decreasing number compared to the nums[i-1]. If increasing, then the previous number must ends with decreasing (in order to satisfy the requirement of a wiggle sequence). So take the last number in the decreasing table, append it to the increasing table and add 1. For decreasing dp table, we simply copy the last number from itself.
The opposite also be could be done easily. And if the numbers are equal, we simply ignore it as a wiggle sequence cannot have difference = 0.
Implementation
Time complexity of this algorithm is $O(n)$. We could further improve its space complexity as we know that in each iteration, the algorithm only checks the last element in both increase / decrease dp table. Therefore, two integer variable would be sufficient for this, making its space complexity to be $O(1)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int lastInc = 1, lastDec = 1;
for (size_t i = 1; i < nums.size(); i++) {
int diff = nums[i] - nums[i-1];
if (diff > 0) {
lastInc = lastDec + 1;
}
else if (diff < 0) {
lastDec = lastInc + 1;
}
}
return max(lastInc, lastDec);
}
};
Here is the implementation in rust, just because I wanted to:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
impl Solution {
pub fn wiggle_max_length(nums: Vec<i32>) -> i32 {
use std::cmp::max;
let (mut inc, mut dec): (i32, i32) = (1, 1);
for i in 1..nums.len() {
let diff = nums[i] - nums[i-1];
if diff > 0 {
inc = dec + 1;
}
else if diff < 0 {
dec = inc + 1;
}
}
return max(inc, dec);
}
}