Skip to main content

1911. Maximum Alternating Subsequence Sum

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

Python​

Bottom Up DP​

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        dp_odd = [0]
        dp_even = [0]

        for num in nums:
            dp_odd.append( max(dp_odd[-1],  dp_even[-1]+num))
            dp_even.append(max(dp_even[-1], dp_odd[-1]-num ))

        return max(dp_even[-1], dp_odd[-1])

Top Down DP​

from functools import cache


class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        @cache
        def dp(i: int, is_choosed: bool):
            if i == len(nums):
                return 0

            num = nums[i] if is_choosed else -nums[i]

            total_choosed = num + dp(i+1, not is_choosed)
            total_skipped = dp(i+1, is_choosed)

            return max(total_choosed, total_skipped)

        return dp(0, True)

Javascript​

var maxAlternatingSum = function(nums) {
    let isUp = false;
    let ans = 0;
    for (let i = 0; i < nums.length; i++) {
        if (isUp && nums[i] < nums[i + 1]) {
            ans -= nums[i]
            isUp = false
        } else if (!isUp && nums[i] > nums[i + 1]) {
            ans += nums[i]
            isUp = true;
        }
        // console.log(ans)
    }
    if (!isUp) ans += nums[nums.length - 1];
    return ans;
};