BinarySearch 0323 Longest Alternating Subsequence

Problem statement

https://binarysearch.com/problems/Longest-Alternating-Subsequence/

Solution

Equal to Leetcode 0376. Wiggle Subsequence.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums):
        @lru_cache(None)
        def dp(i, s):
            if i == 0: return 1
            return dp(i-1, -s) + 1 if (nums[i] - nums[i-1])*s < 0 else dp(i-1, s)
        
        if not nums: return 0
        return max(dp(len(nums)-1, -1), dp(len(nums)-1, 1))