Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/376.html
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
.
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
Follow up: Could you solve this in O(n)
time?
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
-
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_greedy { public int wiggleMaxLength(int[] nums) { if (nums.length < 2) { return nums.length; } int up = 1, down = 1, n = nums.length; for (int i = 1; i < n; ++i) { // start from 2nd if (nums[i] > nums[i - 1]) up = down + 1; else if (nums[i] < nums[i - 1]) down = up + 1; } return Math.min(n, Math.max(up, down)); } } 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]); } } } ############ class Solution { public int wiggleMaxLength(int[] nums) { int up = 1, down = 1; for (int i = 1; i < nums.length; ++i) { if (nums[i] > nums[i - 1]) { up = Math.max(up, down + 1); } else if (nums[i] < nums[i - 1]) { down = Math.max(down, up + 1); } } return Math.max(up, down); } }
-
// OJ: https://leetcode.com/problems/wiggle-subsequence/ // Time: O(N) // Space: O(1) class Solution { public: int wiggleMaxLength(vector<int>& nums) { int inc = 1, dec = 1, N = nums.size(); for (int i = 1; i < N; ++i) { if (nums[i] > nums[i - 1]) inc = dec + 1; else if (nums[i] < nums[i - 1]) dec = inc + 1; } return max(inc, dec); } };
-
class Solution: def wiggleMaxLength(self, nums: List[int]) -> int: up = down = 1 for i in range(1, len(nums)): if nums[i] > nums[i - 1]: up = max(up, down + 1) elif nums[i] < nums[i - 1]: down = max(down, up + 1) return max(up, down) ############ class Solution(object): def wiggleMaxLength(self, nums): """ :type nums: List[int] :rtype: int """ 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)
-
func wiggleMaxLength(nums []int) int { up, down := 1, 1 for i := 1; i < len(nums); i++ { if nums[i] > nums[i-1] { up = max(up, down+1) } else if nums[i] < nums[i-1] { down = max(down, up+1) } } return max(up, down) } func max(a, b int) int { if a > b { return a } return b }
-
function wiggleMaxLength(nums: number[]): number { let up = 1, down = 1; for (let i = 1; i < nums.length; ++i) { let prev = nums[i - 1], cur = nums[i]; if (cur > prev) { up = Math.max(up, down + 1); } else if (cur < prev) { down = Math.max(down, up + 1); } } return Math.max(up, down); }