Description
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.
Examples:
Example 1:
Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).
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] with differences (16, -7, 3, -3, 6, -8).
Example 3:
Input: nums = [1,2,3,4,5,6,7,8,9]
Output: 2Solution in Python
Approach:
- Identify Changes in Direction:
- A sequence “wiggles” when the differences between adjacent numbers change sign (positive to negative or vice versa).
- To achieve the longest wiggle subsequence, each change in direction (from positive to negative or negative to positive) should be part of our sequence.
- Tracking Peaks and Valleys:
- Traverse the array and check the difference between adjacent elements.
- Track the current direction of the difference:
- If the difference is positive, it indicates an “up” wiggle.
- If the difference is negative, it indicates a “down” wiggle.
- Only count a wiggle if it differs in direction from the previous one.
- Greedy Choice:
- This solution uses a greedy approach, updating the count of wiggles each time there is a change in direction. This allows us to avoid using a dynamic programming table or recursion.
Python
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
# Edge case: if there is only one element, the length of the longest wiggle sequence is 1
if len(nums) < 2:
return len(nums)
# Initialize the count to 1, as the first element is always counted in the wiggle sequence
# `prev_diff` holds the previous difference between consecutive numbers
# Start with None since there's no previous difference at the beginning
count = 1
prev_diff = 0 # initialize previous difference as zero
# Iterate over nums from the second element onwards
for i in range(1, len(nums)):
# Calculate the current difference between consecutive elements
diff = nums[i] - nums[i - 1]
# Check if there's a change in the sign of `diff` relative to `prev_diff`
if (diff > 0 and prev_diff <= 0) or (diff < 0 and prev_diff >= 0):
# Increment the count because we have a wiggle (change in direction)
count += 1
# Update `prev_diff` to the current difference
prev_diff = diff
return countExplanation of the Code:
- Initialization:
- If the array has fewer than two elements, return the length of the array as it’s trivially a wiggle sequence.
- Initialize
countto 1, as the first element of the array always counts towards the wiggle sequence. - Initialize
prev_diffto zero to track the initial state of the direction.
- Loop Through Array:
- For each element in
numsstarting from the second element, compute the difference (diff) between it and the previous element. - If
diffhas a different sign thanprev_diff(indicating a change in direction), incrementcountand updateprev_diffto the currentdiff.
- For each element in
- Return Result:
- The
countvariable will have the length of the longest wiggle subsequence.
- The
Solution in C++
C++
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
// If the array has one element or less, return the size of the array.
// Any single element sequence is trivially a wiggle sequence.
int n = nums.size();
if (n < 2) return n;
// Initialize variables to count the up and down subsequences.
// 'up' will track the length of the longest subsequence ending in an "up" wiggle (positive difference).
// 'down' will track the length of the longest subsequence ending in a "down" wiggle (negative difference).
int up = 1, down = 1;
// Iterate through the array starting from the second element.
for (int i = 1; i < n; ++i) {
// Calculate the difference between the current and previous element.
int diff = nums[i] - nums[i - 1];
if (diff > 0) {
// If difference is positive, we have an "up" wiggle.
// Update 'up' as the previous 'down' + 1, because an "up" can follow a "down" wiggle.
up = down + 1;
} else if (diff < 0) {
// If difference is negative, we have a "down" wiggle.
// Update 'down' as the previous 'up' + 1, because a "down" can follow an "up" wiggle.
down = up + 1;
}
// If diff == 0, do nothing, as consecutive equal elements do not form a wiggle.
}
// The maximum wiggle sequence length will be the larger of the two.
return max(up, down);
}
};Solution in Javascript
JavaScript
var wiggleMaxLength = function(nums) {
// If the input array is empty or has only one element, return the length of nums (either 0 or 1).
if (nums.length < 2) return nums.length;
// Initialize two variables to track the length of the longest wiggle subsequence:
// up: the longest wiggle subsequence that ends in a positive difference.
// down: the longest wiggle subsequence that ends in a negative difference.
let up = 1;
let down = 1;
// Iterate through the array starting from the second element.
for (let i = 1; i < nums.length; i++) {
// Calculate the difference between the current element and the previous one.
let diff = nums[i] - nums[i - 1];
// If the difference is positive, it means there's an "up" wiggle.
if (diff > 0) {
// Update the 'up' count by adding 1 to 'down' (the previous longest wiggle subsequence ending in a "down").
up = down + 1;
}
// If the difference is negative, it means there's a "down" wiggle.
else if (diff < 0) {
// Update the 'down' count by adding 1 to 'up' (the previous longest wiggle subsequence ending in an "up").
down = up + 1;
}
// If diff is zero, ignore it because consecutive equal elements don't affect the wiggle pattern.
}
// The result is the maximum length of wiggle subsequences ending in either up or down.
return Math.max(up, down);
};Solution in Java
Java
class Solution {
public int wiggleMaxLength(int[] nums) {
// If the array has less than two elements, it's trivially a wiggle sequence
if (nums.length < 2) {
return nums.length;
}
// Initialize two variables to track the length of wiggle subsequences
// 'up' represents the longest subsequence ending with an increasing difference
// 'down' represents the longest subsequence ending with a decreasing difference
int up = 1;
int down = 1;
// Traverse the array starting from the second element
for (int i = 1; i < nums.length; i++) {
// Calculate the difference between the current element and the previous element
int diff = nums[i] - nums[i - 1];
if (diff > 0) {
// If the difference is positive, this is an "up" wiggle
// We increment the 'up' variable based on the previous 'down' length
up = down + 1;
} else if (diff < 0) {
// If the difference is negative, this is a "down" wiggle
// We increment the 'down' variable based on the previous 'up' length
down = up + 1;
}
// If diff == 0, we do nothing as no wiggle occurs
}
// The result is the maximum length of a wiggle subsequence,
// which can end in either an "up" or "down" wiggle
return Math.max(up, down);
}
}