Wiggle Subsequence
Problem
A wiggle sequence has alternating positive/negative differences between consecutive terms. Return the length of the longest wiggle subsequence of nums.
nums = [1, 7, 4, 9, 2, 5]6def wiggle_max_length(nums):
if not nums:
return 0
up = down = 1
for i in range(1, len(nums)):
if nums[i] > nums[i - 1]:
up = down + 1
elif nums[i] < nums[i - 1]:
down = up + 1
return max(up, down)function wiggleMaxLength(nums) {
if (!nums.length) return 0;
let up = 1, down = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) up = down + 1;
else if (nums[i] < nums[i - 1]) down = up + 1;
}
return Math.max(up, down);
}class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length == 0) return 0;
int up = 1, down = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) up = down + 1;
else if (nums[i] < nums[i - 1]) down = up + 1;
}
return Math.max(up, down);
}
}int wiggleMaxLength(vector<int>& nums) {
if (nums.empty()) return 0;
int up = 1, down = 1;
for (int i = 1; i < (int)nums.size(); i++) {
if (nums[i] > nums[i - 1]) up = down + 1;
else if (nums[i] < nums[i - 1]) down = up + 1;
}
return max(up, down);
}Explanation
A wiggle sequence alternates between going up and going down. The neat idea is that we only need to track two numbers as we scan: up = the longest wiggle ending with a rise, and down = the longest wiggle ending with a fall.
Both start at 1 (a single element is a trivial wiggle). Then for each new element we compare it to the previous one.
If it rose (nums[i] > nums[i-1]), the last move was up, so it must extend a sequence that previously ended down: up = down + 1. If it fell, similarly down = up + 1. If it's equal, nothing changes.
This works because each new direction can only build on the opposite-direction state, which automatically enforces the alternation. We never need to look back further than these two running values.
Example: nums = [1,7,4,9,2,5] rises and falls at every step, so the whole array is one big wiggle. up and down keep leapfrogging, and the answer max(up, down) is 6.