[LeetCode] 376. Wiggle Subsequence

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

Intuitive DP solution:

dp[i][0] = length of the longest up-wiggle sequence ends by i-th number

dp[i][1] = length of the longest down-wiggle sequence ends by i-th number

Update dp[i][0] and dp[i][1] by comparing nums[i] with all numbers before it.

Time complexity = O ( N ** 2 )

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        N = len(nums)
        
        if N < 2: return N
        
        dp = [[0, 0] for _ in range(N)]
        dp[0][0] = dp[0][1] = 1
        
        result = 0
        
        for i in range(N):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i][0] = max(dp[i][0], dp[j][1] + 1)
                elif nums[i] < nums[j]:
                    dp[i][1] = max(dp[i][1], dp[j][0] + 1)
            
            result = max(result, dp[i][0], dp[i][1])
        
        return result

Linear DP solution:

up[i] = length of the longest up-wiggle sequence in section nums[0:i+1].

down[i] = length of the longest down-wiggle sequence in section nums[0:i+1]

Be aware, the longest up / down wiggle sequence is not necessary ends by nums[i].

For every nums[i], there could be 3 cases:

When nums[i] == nums[i-1]: 

nums[i] cannot extend either previous up-wiggle or down-wiggle sequence,

up[i] = up[i-1], down[i] = down[i-1]

When nums[i] < nums[i-1]:

nums[i] can be appended to previous down-wiggle sequence  and create a longer up-wiggle sequence, up[i] = down[i-1] + 1

nums[i] cannot be appended to previous up-wiggle sequence to create a longer down-wiggle sequence.

So, length of the longest down-wiggle sequence in section nums[0:i+1] does not change.

down[i] = down[i-1]

When nums[i] > nums[i-1]:

nums[i] can be appended to previous up-wiggle sequence and create a longer down-wiggle sequence,

down[i] = up[i-1] + 1

nums[i] cannot be appended to previous down-wiggle sequence to create a longer up-wiggle sequence.

So, length of the longest up-wiggle sequence in section nums[0:i+1] does not change.

up[i] = up[i-1]

Time Complexity = O ( N )

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

Because for i-th number, it only compares the previous number to update the up / down wiggle sequence of section nums[0:i+1].

It only needs 2 variables to the save the length of up-wiggle and down-wiggle sequence of section nums[0:i]

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

        up = down = 1
        
        for i in range(1, N):
            if nums[i] > nums[i-1]:
                up = down + 1
            elif nums[i] < nums[i-1]:
                down = up + 1

        return max(up, down)