LeetCode: Wiggle Subsequence – Prepare For Coder Interview

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
}

Post Views: 0