Wiggle Subsequence

Similar Problems:

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?

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution: dp[i][0]/dp[i][1]: the size of longest subsequence, which may or may not choose nums[i]

// https://code.dennyzhang.com/wiggle-subsequence // Basic Ideas: dynamic programming // // down[i]: longest subsequence with a down pair as the last element // up[i] // // Complexity: Time O(n), Space O(n) func max(x, y int) int { if x>y { return x } else { return y } } func wiggleMaxLength(nums []int) int { if len(nums) == 0 { return 0 } down, up := make([]int, len(nums)), make([]int, len(nums)) down[0], up[0] = 1, 1 for i:=1; i<len(nums); i++ { if nums[i] == nums[i-1] { up[i] = up[i-1] down[i] = down[i-1] } else { if nums[i] > nums[i-1] { up[i] = down[i-1]+1 down[i] = down[i-1] } else { down[i] = up[i-1]+1 up[i] = up[i-1] } } } return max(down[len(nums)-1], up[len(nums)-1]) }

- Solution: dp[i][0]/dp[i][1]: the size of longest subsequence, which may or may not choose nums[i]

// https://code.dennyzhang.com/wiggle-subsequence // Basic Ideas: dynamic programming // // down[i]: longest subsequence with a down pair as the last element // up[i] // // Complexity: Time O(n*n), Space O(n) func max(x, y int) int { if x>y { return x } else { return y } } func wiggleMaxLength(nums []int) int { if len(nums) == 0 { return 0 } down, up := make([]int, len(nums)), make([]int, len(nums)) down[0], up[0] = 1, 1 for i:=1; i<len(nums); i++ { down[i], up[i] = down[i-1], up[i-1] for j:=i-1; j>=0; j-- { if nums[j] > nums[i] { down[i] = max(down[i], up[j]+1) } if nums[j] < nums[i] { up[i] = max(up[i], down[j]+1) } } } return max(down[len(nums)-1], up[len(nums)-1]) }

- Solution: dp[i][0]/dp[i][1]: the size of longest subsequence, when choosing choose nums[i]

// https://code.dennyzhang.com/wiggle-subsequence // Basic Ideas: dynamic programming // // down[i]: choose nums[i], and it can come as a down pair as the last element // up[i] // // Complexity: Time O(n*n), Space O(n) func max(x, y int) int { if x>y { return x } else { return y } } func wiggleMaxLength(nums []int) int { if len(nums) == 0 { return 0 } res := 1 down, up := make([]int, len(nums)), make([]int, len(nums)) down[0], up[0] = 1, 1 for i:=1; i<len(nums); i++ { down[i], up[i] = 1, 1 for j:=i-1; j>=0; j-- { if nums[j] > nums[i] { down[i] = max(down[i], up[j]+1) } if nums[j] < nums[i] { up[i] = max(up[i], down[j]+1) } } res = max(max(res, down[i]), up[i]) } return res }