leetcode 1911 最大子序列交替和

一个下标从 0 开始的数组的 交替和 定义为 偶数 下标处元素之 和 减去 奇数 下标处元素之 和 。

比方说，数组 [4,2,5,3] 的交替和为 (4 + 5) - (2 + 3) = 4 。
给你一个数组 nums ，请你返回 nums 中任意子序列的 最大交替和 （子序列的下标 重新 从 0 开始编号）。

一个数组的 子序列 是从原数组中删除一些元素后（也可能一个也不删除）剩余元素不改变顺序组成的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的一个子序列（加粗元素），但是 [2,4,2] 不是。

示例 1：

输入：nums = [4,2,5,3]
输出：7
解释：最优子序列为 [4,2,5] ，交替和为 (4 + 5) - 2 = 7 。
示例 2：

输入：nums = [5,6,7,8]
输出：8
解释：最优子序列为 [8] ，交替和为 8 。
示例 3：

输入：nums = [6,2,1,2,4,5]
输出：10
解释：最优子序列为 [6,1,5] ，交替和为 (6 + 5) - 1 = 10 。

even[i] 表示在下标[0-i] (闭区间)里面选元素，形成的子序列长度为偶数的时候，的最大交替和
odd[i] 表示在下标[0-i] (闭区间)里面选元素，形成的子序列长度为奇数的时候，的最大交替和

则在遍历到nums[i]的时候，
1 如果要选nums[i],
1.1 如果选择nums[i]且形成偶数长度的子序列，即对应even[i]，那么不选的时候就是奇数，要让even[i]呈现出最大交替和，不选的时候的奇数子序列最大交替和也必须是最大的，即even[i] = odd[i-1] - nums[i]
1.2 如果选择nums[i]且形成奇数长度的子序列，即对应odd[i]，那么不选的时候就是偶数，要让odd[i]呈现出最大交替和，不选的时候的偶数子序列最大交替和也必须是最大的，即odd[i] = even[i-1] + nums[i]

2 如果不选择nums[i]
2.1 对于even[i]来说，既然没有加入nums[i], 那么没考虑nums[i]之前的偶数长度子序列even[i-1]就是考虑了nums[i]之后的偶数长度子序列，即even[i] = even[i-1]
2.2 对于odd[i]来说，既然没有加入nums[i], 那么没考虑nums[i]之前的奇数长度子序列odd[i-1]就是考虑了nums[i]之后的奇数长度子序列，即odd[i] = odd[i-1]

综上even[i] = max(odd[i-1] - nums[i], even[i-1])
odd[i] = max(even[i-1] + nums[i], odd[i-1])

下面要确定边界了，在考虑第一个元素的时候，即even[0]和odd[0]应该如何初始化：
1 even[0]即仅考虑第一个元素的时候且形成了偶数长度的子序列，那其实就是什么都没有加，即even[0] = 0
2 odd[0]即仅考虑第一个元素的时候且形成了奇数长度的子序列，那其实就是把第一个元素加进来了，由于这个子序列只有一个元素，在子序列里面下标为0，由题目的定义，最大交替和为这个元素本身，即even[0] = nums[0]

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

最后，可以看到我们的当前状态i是从i-1转移来的，因此只需要维持一个当前值就可以了，这样空间复杂度可以降低到O（1）。并且其实只需要返回最后是奇数长度子序列的结果，因为一定比偶数长度的时候大。

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