Wiggle subsequence in Java
A wiggle subsequence is a sequence of numbers where the differences between successive elements alternate between positive and negative. For example, a subsequence `[nums[i1], nums[i2],..., nums[ik]]` is a wiggle subsequence if the sign of `nums[i(j+1)] - nums[ij]` is different for all `1 <= j < k`.
Example 1:
Input: [1, 7, 4, 9, 2, 5]
Output: [1, 7, 4, 9, 2]
Explanation: The following elements differ from one another: 6 (positive), -3 (negative), 5 (positive), and -7 (negative). The subsequence [1, 7, 4, 9, 2] is a wiggle subsequence because the differences alternate between positive and negative values.
Example 2:
Input:[1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
Output:[1, 17, 5, 15, 5, 16]
Explanation: 16 (positive), -12 (negative), 5 (positive), 3 (positive), 2 (positive), -5 (negative), -5 (negative), 11 (positive), and -8 (negative) are the differences between the elements that come after each other. The subsequence [1, 17, 5, 15, 5, 16] exhibits a wiggle pattern due to the alternating positive and negative differences.
Approach: Using Dynamic Programming
The dynamic programming method uses two arrays to track the length of the longest wiggle subsequence, one during up and the other during down trends.
Here's the implementation of the dynamic programming approach of finding the longest length of wiggle subsequence:
FileName:WiggleSubsequence.java
public class WiggleSubsequence {
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) {
return nums.length;
}
int[] up = new int[nums.length];
int[] down = new int[nums.length];
up[0] = down[0] = 1;
for (int i = 1; i < nums.length; i++) {
// If the current number is greater than the previous number, the trend is up
if (nums[i] > nums[i - 1]) {
// Extend the up trend by one element, considering the previous element was in a down trend
up[i] = down[i - 1] + 1;
down[i] = down[i - 1];
}
// If the current number is less than the previous number, the trend is down
else if (nums[i] < nums[i - 1]) {
down[i] = up[i - 1] + 1;
up[i] = up[i - 1]; // Keep the up length the same
}
// If the current number is equal to the previous number, there is no change in the trend
else {
up[i] = up[i - 1];
down[i] = down[i - 1];
}
}
return Math.max(up[nums.length - 1], down[nums.length - 1]);
}
public static void main(String args[]) {
int[] nums = {1, 7, 4, 9, 2, 5};
WiggleSubsequence solution = new WiggleSubsequence();
System.out.println("Length of the longest wiggle subsequence: " + solution.wiggleMaxLength(nums));
}
}
Output:
Length of the longest wiggle subsequence: 6
Complexity analysis: The dynamic programming approach has a linear time and space complexity of O(n) due to the time complexity of initializing two arrays of length `n` and the time complexity of iterating through the input sequence once, considering each element. The total space complexity is O(n) for the additional array.
Using Optimized Approach
An optimized approach to finding the length of the longest wiggle subsequence involves initializing two variables, up and down, to track the last element and its direction. It reduces space complexity compared to storing the entire subsequence. Iterating through the input sequence, the length of the longest wiggle subsequence is determined by the maximum value between up and down, considering the previous element's up or down trend.
Here's the implementation of an optimized approach to find the length of the longest wiggle subsequence:
FileName:WiggleSubsequence1.java
public class WiggleSubsequence1 {
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) {
return nums.length;
}
int up = 1, down = 1;
for (int i = 1; i < nums.length; i++) {
// Check if the current element is greater than the previous element
if (nums[i] > nums[i - 1]) {
// If the current element is greater, update 'up' to be 'down + 1'
up = down + 1;
}
// Check if the current element is less than the previous element
else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
public static void main(String args[]) {
int[] nums = {1, 7, 4, 9, 2, 5};
WiggleSubsequence1 solution = new WiggleSubsequence1();
System.out.println("Length of the longest wiggle subsequence: " + solution.wiggleMaxLength(nums));
}
}
Output:
Length of the longest wiggle subsequence: 6
Complexity analysis: The optimized approach for finding the length of the longest wiggle subsequence has a time complexity of O(n) due to iterating through the input sequence and using a constant number of additional variables (up and down), and a space complexity of O(1) due to the use of additional variables.