Leetcode 1911. Maximum Alternating Subsequence Sum

Problem statement

https://leetcode.com/problems/maximum-alternating-subsequence-sum/

Solution

This is nice and easy dynamic programming problem. Let dp1[k] be the maximum Alternating Subsequence Sum if we reached element with index i and the last element we taken was with negative sign. dp2[k] means that last element we taken was with positive sign. Then to update elements we have two options:

1. For dp1[k] we need to check dp1[k-1] and dp2[k-1] - nums[k], because last sign was + and if we take nums[k], we need to take it with minus sign.
2. For dp2[k] we need to check dp2[k-1] and dp1[k-1] + nums[k], because last sign was - and if we take nums[k], we need to take it with plus sign.

Complexity

Time complexity is O(n), space complexity as well. Note, that space complexity can be reduced to O(1).

Code

class Solution:
    def maxAlternatingSum(self, nums):
        n = len(nums)
        dp1, dp2 = [0]*(n+1), [0]*(n+1)

        for k in range(n):
            dp1[k] = max(dp2[k-1] - nums[k], dp1[k-1])
            dp2[k] = max(dp1[k-1] + nums[k], dp2[k-1])
        
        return max(dp1[-2], dp2[-2])