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

Define by dp(i, 1) the biggest length of wiggle subsequense, which ends with element nums[i] and has and increasing status, and dp(i, -1) is the biggest length of wiggle subsequence, which ends with element nums[i] and has decreasing status.

How we can calculate dp(i, 1), looking at previous element nums[i-1]:

  1. if nums[i-1] < nums[i], then it means that we need to look at dp(i - 1, -1) + 1: look at the biggest subsequence ending in i-1, which have decreasing status and add 1, because we can continue it by one element.
  2. if nums[i-1] >= nums[i], then we can not continue subsequence with decreasing status, all we can do is to look at dp(i-1, 1).
  3. Very similar logic is used to calculate dp(i, -1). Here I write both cases in very compact way in one line.

Note also that here we can say we use greedy approach: it is always enough to take previous element nums[i-1] to continue to build our subsequence, the logic is the following: actually what matters are local extremums in our array. Imagine, that we have part of array like this 100, 1, 2, 5, 10, 13, 20, 1. What can we say about part 1, 2, 5, 10, 13, 20? We can take only 2 elements, and the best case will be to take 1 and 20.

Complexity: time complexity is O(n), space complexity is O(n) as well, which potentially can be reduced to O(1).

class Solution:
    def wiggleMaxLength(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)
            
        return max(dp(len(nums)-1, -1), dp(len(nums)-1, 1))

If you like the solution, you can upvote it on leetcode discussion section: Problem 0376