Question
Formatted question description: https://leetcode.ca/all/376.html
376 Wiggle Subsequence
A sequence of numbers is called a wiggle sequence if 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 fewer than two elements is trivially a wiggle sequence.
For example,
[1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative.
In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive
and the second because its last difference is zero.
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence.
A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence,
leaving the remaining elements in their original order.
Example 1:
Input: [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence.
Example 2:
Input: [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].
Example 3:
Input: [1,2,3,4,5,6,7,8,9]
Output: 2
Follow up:
Can you do it in O(n) time?
@tag-dp
Algorithm
DP
We maintain two dp arrays p and q,
p[i]
indicates the maximum length of the swing subsequence with a positive first difference when the position i is reachedq[i]
indicates the maximum length of the wobble sub-sequence with a negative first difference when reaching the i position
We traverse the array from i=1, and then for each traversed number, traverse to this number from the beginning position, then compare nums[i] and nums[j], and update the corresponding positions respectively.
Greedy
Maintain two variables p and q, and then traverse the array
- If the current number is greater than the previous number, then
p=q+1
- If the current number is smaller than the previous number, then
q=p+1
Finally, compare the larger value of p and q with n, and choose the smaller one.
Code
Java
import java.util.Arrays;
public class Wiggle_Subsequence {
public static void main(String[] args) {
Wiggle_Subsequence out = new Wiggle_Subsequence();
Solution s = out.new Solution();
System.out.println(s.wiggleMaxLength(new int[]{1,17,5,10,13,15,10,5,16,8}));
}
public class Solution_better_oN {
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) {
return nums.length;
}
int n = nums.length;
int[] up = new int[n];
int[] down = new int[n];
up[0] = down[0] = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up[i] = down[i - 1] + 1;
down[i] = down[i - 1];
} else if (nums[i] < nums[i - 1]) {
down[i] = up[i - 1] + 1;
up[i] = up[i - 1];
} else { // @note: test case, input: [0,0]
down[i] = down[i - 1];
up[i] = up[i - 1];
}
}
return Math.max(down[n - 1], up[n - 1]);
}
}
public class Solution { // o(N^2)
// @note: could start with either up or down, both valid
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) {
return nums.length;
}
// up[i] refers to the length of the longest wiggle subsequence obtained so far
// considering i^th element as the last element of the wiggle subsequence and ending with a rising wiggle.
int[] up = new int[nums.length];
int[] down = new int[nums.length];
Arrays.fill(up, 1); // initialization, each position is at least 1 for that char
Arrays.fill(down, 1); // @note: or don't do this step, in final return just `1+()`
for (int i = 1; i < nums.length; i++) {
for(int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
up[i] = Math.max(up[i],down[j] + 1);
} else if (nums[i] < nums[j]) {
down[i] = Math.max(down[i],up[j] + 1);
}
}
}
return Math.max(down[nums.length - 1], up[nums.length - 1]);
}
}
public class Solution_greedy {
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) {
return nums.length;
}
int p = 1, q = 1, n = nums.length;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i - 1]) p = q + 1;
else if (nums[i] < nums[i - 1]) q = p + 1;
}
return Math.min(n, Math.max(p, q));
}
}
}