1911. Maximum Alternating Subsequence Sum - Explanation

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        def dfs(i, even):
            if i == len(nums):
                return 0
            total = nums[i] if even else -nums[i]
            return max(total + dfs(i + 1, not even), dfs(i + 1, even))

        return dfs(0, True)

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        dp = {}

        def dfs(i, even):
            if i == len(nums):
                return 0
            if (i, even) in dp:
                return dp[(i, even)]

            total = nums[i] if even else -nums[i]
            dp[(i, even)] = max(total + dfs(i + 1, not even), dfs(i + 1, even))
            return dp[(i, even)]

        return dfs(0, True)

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0] * 2 for _ in range(n + 1)]  # dp[i][0] -> odd, dp[i][1] -> even

        for i in range(n - 1, -1, -1):
            dp[i][1] = max(nums[i] + dp[i + 1][0], dp[i + 1][1])  # even
            dp[i][0] = max(-nums[i] + dp[i + 1][1], dp[i + 1][0])  # odd

        return dp[0][1]

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

        for i in range(len(nums) - 1, -1, -1):
            tmpEven = max(sumOdd + nums[i], sumEven)
            tmpOdd = max(sumEven - nums[i], sumOdd)
            sumEven, sumOdd = tmpEven, tmpOdd

        return sumEven