
Problem Statement
In the context of arrays, a wiggle sequence is defined as a sequence where the differences between successive numbers in the sequence strictly alternate between positive and negative. The initial difference in the sequence could either be positive or negative. Notably, a single element sequence, as well as any two-element sequence with distinct numbers, automatically qualify as wiggle sequences.
To elaborate, consider the sequence [1, 7, 4, 9, 2, 5]
which qualifies as a wiggle sequence. This is deduced from the difference between successive elements: (6, -3, 5, -7, 3)
, which alternates between positive and negative. Conversely, [1, 4, 7, 2, 5]
and [1, 7, 4, 5, 5]
do not meet the criteria for a wiggle sequence. The former sequence has its first two differences as positive and hence does not alternate, while the latter has a difference of zero which is neither positive nor negative.
A subsequence is defined as a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. Given an integer array nums
, the task is to determine the length of the longest wiggle subsequence within 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:
2
Constraints
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
Approach and Intuition
A nuanced understanding of the problem can be attributed to the observation of changes in the trend of the sequence. When considering how to determine the longest wiggle subsequence, a straightforward method involves:
- Define a default sequence starting with the first two distinct elements which establish the initial trend (either increasing or decreasing).
- Traverse through the array and compare each element to the previous one to detect a change in the gradient (from increasing to decreasing or vice versa).
- Whenever a change in the trend is observed, include that element in the wiggle subsequence. This captures the point where the sequence wiggles.
- Continue this until all elements are assessed.
This simpler greedy approach leverages capturing each point of transition to construct the longest possible wiggle sequence.
Understanding Through Examples:
Example 1: For input
nums = [1,7,4,9,2,5]
, we observe that the entire sequence forms a wiggle pattern. Hence, the longest wiggle subsequence includes all elements, so the output is6
.Example 2: For input
nums = [1,17,5,10,13,15,10,5,16,8]
, a possible longest wiggle subsequence could be[1, 17, 5, 10, 13, 10, 16, 8]
. This subsequence has consistent alternation between rise and fall, giving a length of7
.Example 3: Given
nums = [1,2,3,4,5,6,7,8,9]
, this array is consistently increasing, thus only two elements can be used to form a valid wiggle subsequence (e.g.,[1, 2]
or any two consecutive numbers), resulting in the maximum length being2
.
By following these intuitions and steps, we can efficiently determine the length of the longest wiggle subsequence without needing any advanced data structures, utilizing basic array manipulations and conditional assessments.
Solutions
- Java
public class Solution {
public int getMaxWiggleLength(int[] sequence) {
if (sequence.length < 2)
return sequence.length;
int lastDifference = sequence[1] - sequence[0];
int length = lastDifference != 0 ? 2 : 1;
for (int index = 2; index < sequence.length; index++) {
int currentDiff = sequence[index] - sequence[index - 1];
if ((currentDiff > 0 && lastDifference <= 0) || (currentDiff < 0 && lastDifference >= 0)) {
length++;
lastDifference = currentDiff;
}
}
return length;
}
}
The given Java solution is designed to calculate the maximum length of a wiggle subsequence from an input array. A wiggle subsequence is one where the differences between successive elements strictly alternate between positive and negative. Here's how this solution works:
- Check if the input sequence has fewer than two elements. If so, return the length of the sequence, as a sequence with less than two elements doesn't have enough items to wiggle.
- Initialize
lastDifference
to capture the difference between the first two elements of the sequence. This will help track the last direction of wiggle (up or down). - Set
length
of the wiggle subsequence. If the first difference is non-zero (indicative of a wiggle start), set length to 2. Otherwise, set it to 1 as there's no wiggle with only identical or single element. - Iterate through the sequence starting from the third element:
- Calculate the current difference between the current and the previous element.
- Check if the current difference and the last difference change signs (one is positive and the other is negative or zero and vice versa). This change in sign indicates a wiggle.
- If a wiggle is detected, increment the
length
of the wiggle subsequence and updatelastDifference
to the current difference.
- Return the computed
length
, which will be the maximum length of the wiggle subsequence.
This solution efficiently determines the maximum wiggle sequence length in a single pass through the input array with a time complexity of O(n), where n is the number of elements in the sequence.
No comments yet.