376. Wiggle Subsequence

Problem Link

Solution 1: Greedy

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        L = len(nums)
        if L == 1:
            return 1
        res = 1
        diff = nums[1] - nums[0]
        if diff != 0:
            res += 1
        for i in range(2, L):
            if diff >= 0 and nums[i] - nums[i-1] < 0: # diff == 0 only happens when nums[1] - nums[0] == 0
                res += 1
                diff = nums[i] - nums[i-1]
            elif diff <= 0 and nums[i] - nums[i-1] > 0:
                res += 1
                diff = nums[i] - nums[i-1]
        return res

Analysis:

• Time complexity : O(n)
• Spacecomplexity : O(1).

Solution 2: Dynamic Programming

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        L = len(nums)
        up = [1] * L
        down = [1] * L
        res = 1
        for i in range(L):
            for j in range(i):
                if nums[j] < nums[i]:
                    up[i] = max(up[i], down[j] + 1)
                elif nums[j] > nums[i]:
                    down[i] = max(down[i], up[j] + 1)
                res = max(res, up[i], down[i])
        return res

Analysis:

• Time complexity : O(n^2)
• Space complexity : O(n). Two arrays of the same length are used.