376. Wiggle Subsequence

https://leetcode.com/problems/wiggle-subsequence/

Python

Bottom-Up DP

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if (length := len(nums)) < 2:
            return length

        dp_up, dp_down = [0]*len(nums), [0]*len(nums)

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp_up[i] = max(dp_up[i], dp_down[j]+1)
                elif nums[i] < nums[j]:
                    dp_down[i] = max(dp_down[i], dp_up[j]+1)

        return 1 + max(dp_up[-1], dp_down[-1])