376.Wiggle Subsequence

Tags: [DP]

Link: https://leetcode.com/problems/wiggle-subsequence/\#/description

A sequence of numbers is called awiggle sequenceif 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.

Examples:

Input: [1,7,4,9,2,5]

Output: 6
The entire sequence is a wiggle sequence.


Input: [1,17,5,10,13,15,10,5,16,8]

Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]

Output: 2

Follow up:
Can you do it in O(n) time?

Credits:
Special thanks to @agave and @StefanPochmann for adding this problem and creating all test cases.

Solution: DP

class Solution(object):
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        nums_len = len(nums)
        up = [0 for _ in xrange(nums_len)]
        down = [0 for _ in xrange(nums_len)]

        up[0] = 1
        down[0] = 1

        for i in xrange(1, nums_len):
            prev = nums[i - 1]
            curr = nums[i]

            if prev < curr:
                up[i] = down[i - 1] + 1
                down[i] = down[i - 1]
            elif prev > curr:
                down[i] = up[i - 1] + 1
                up[i] = up[i - 1]
            else:
                # prev == curr:
                up[i] = up[i - 1]
                down[i] = down[i - 1]

        return max(up[nums_len - 1], down[nums_len - 1])

Revelation:

• If prev < curr, go up, which means the previous state should go down. So the current current wiggle sequence length should be down[i - 1] + 1, and we record this to up memo, so up[i] = down[i - 1] + 1. And at the same time, the down memo doesn't get changed, so down[i] = down[i - 1].
• If prev > curr, go down, we do the similar thing, down[i] = up[i - 1] + 1, and up[i] = up[i - 1].
• If prev == curr, up[i] = up[i - 1], and down[i] = down[i - 1].
• When we use DP(dynamic programming) to solve the problem, we can think about using multiple memos.
• Maybe sometime, before diving into DP, we can think whether the problem can be solved by greedy approach.

Note:

• Time complexity = O(n), n is the number of given elements.

Time Limited Exceeded

class Solution(object):
    def __init__(self):
        self.max_len = 0

    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        buff = []
        self.wiggle_max_len_helper(nums, 0, buff)
        return self.max_len

    def wiggle_max_len_helper(self, nums, index, buff):
        # base case
        if index >= len(nums):
            self.max_len = max(self.max_len, len(buff))
            return

        for i in xrange(index, len(nums)):
            if self.is_valid(buff, nums[i]):
                buff.append(nums[i])
                self.wiggle_max_len_helper(nums, i + 1, buff)
                buff.pop()

            self.wiggle_max_len_helper(nums, i + 1, buff)

    def is_valid(self, buff, curr):
        if not buff:
            return True
        elif len(buff) == 1:
            return buff[-1] != curr

        return (buff[-1] - buff[-2]) * (curr - buff[-1]) < 0

Revelation:

• For each element, if it doesn't violate the constraint, we can choose pick it or not.

Note:

• Time complexity = O(2^n), n is the number of given elements.