最大交替子序列和（Maximum Alternating Subsequence Sum）
题目描述
给定一个整数数组 nums，定义交替子序列为：从 nums 中选取一个子序列（不一定连续），使得选取的元素按照原顺序交替进行加减运算。例如，子序列 [a1, a2, a3, a4, ...] 对应的交替和为：a1 - a2 + a3 - a4 + ...（加减交替出现，从加号开始）。请你计算所有可能交替子序列中，能得到的最大交替和，并返回该值。
示例
输入：nums = [4,2,5,3]
解释：选择子序列 [4, 2, 5]，交替和 = 4 - 2 + 5 = 7；选择 [4, 2, 3]，交替和 = 4 - 2 + 3 = 5；选择 [4, 5]，交替和 = 4 - 5 = -1；选择 [4]，交替和 = 4。最大为 7。
输出：7
约束条件
1 <= nums.length <= 10^51 <= nums[i] <= 10^5
解题过程循序渐进讲解
第一步：理解问题核心
我们需要从数组中选出一个子序列（顺序不变），并赋予它们交替的符号（正、负、正、负……，从正号开始），使得这个带符号的序列和最大。
关键点：
- 子序列可以不连续，但顺序必须保持。
- 符号交替起始为“+”。
- 目标：最大化带符号的和。
简单尝试
如果我们只选一个数，符号为正，和就是该数本身。
如果选两个数 [a, b]，和为 a - b。
如果选三个数 [a, b, c]，和为 a - b + c。
可见，奇数位置的元素（在原序列中按选中顺序）贡献为正，偶数位置的贡献为负。
问题本质：如何选择元素，让正项之和尽可能大，负项之和尽可能小（或说绝对值小）。
第二步：动态规划状态定义
由于符号交替取决于该元素在子序列中的位置是奇数还是偶数，我们可以设计两个状态来分别表示当前考虑的元素在子序列中的“位置奇偶性”对应的最大交替和。
设：
dp_even[i]：表示考虑前i个元素（nums[0..i-1]），并且最后选中的元素在子序列中的位置是偶数时，能得到的最大交替和。dp_odd[i]：表示考虑前i个元素，并且最后选中的元素在子序列中的位置是奇数时，能得到的最大交替和。
位置编号从 1 开始：
- 如果最后选中的元素是子序列中第 1 个（奇数位置），它的符号是
+。 - 如果最后选中的元素是子序列中第 2 个（偶数位置），它的符号是
-。 - 如果最后选中的元素是子序列中第 3 个（奇数位置），符号又是
+，以此类推。
为什么这样定义？
因为我们计算交替和时，需要知道当前元素是加还是减，这取决于它在子序列中是第几个被选的。
第三步：状态转移分析
考虑第 i 个元素 nums[i-1]（索引从 0 开始，为了清晰用 1-based 思考）。
情况 1：我们不选 nums[i-1]
那么 dp_even[i] 和 dp_odd[i] 应该继承前 i-1 个元素的结果：
dp_even[i] = dp_even[i-1]
dp_odd[i] = dp_odd[i-1]
情况 2：我们选 nums[i-1] 作为子序列的一个元素
- 如果它被选为奇数位置（即符号为
+），那么它前面可以接一个偶数位置的元素，也可以不接（即它是子序列的第一个元素）。
状态转移：dp_odd[i] = max(dp_even[i-1] + nums[i-1], nums[i-1])
解释：dp_even[i-1] + nums[i-1]：前面已有一个偶数位置的元素，现在接一个奇数位置的，符号为+。nums[i-1]：直接以该元素开始一个新的子序列，位置为奇数，符号为+。
- 如果它被选为偶数位置（即符号为
-），那么它前面必须接一个奇数位置的元素（因为偶数位置前面必须是奇数位置，否则无法形成交替）。
状态转移：dp_even[i] = dp_odd[i-1] - nums[i-1]
解释：前面已有一个奇数位置的元素，现在接一个偶数位置的，符号为-。
综合两种情况：对于每个 i，我们取选与不选中的最大值。
所以：
dp_odd[i] = max(dp_odd[i-1], dp_even[i-1] + nums[i-1], nums[i-1])dp_even[i] = max(dp_even[i-1], dp_odd[i-1] - nums[i-1])
注意：dp_even[i] 的初始情况：如果前面没有奇数位置元素，不能单独以偶数位置开始，所以 dp_even[0] 应该初始化为一个很小的值（例如 -inf），但实际上我们可以通过转移式避免：因为 dp_odd[i-1] 可能是负的，但 dp_even[i] 可以选择不选当前元素，继承 dp_even[i-1]。而 dp_even[0]（前 0 个元素）应该为 0 吗？不对，因为前 0 个元素不可能有偶数位置的结尾。仔细分析：
第四步：初始化和边界
定义 dp_odd[0] = 0，dp_even[0] = 0？我们试试：
-
对于空序列，没有“最后选中的元素”，所以两个状态都可以视为 0？不行，因为偶数位置要求前面必须有奇数位置，空序列不可能有偶数位置结尾。更安全的做法：设
dp_odd[0] = 0，dp_even[0] = -inf（极小值），表示不可能状态。但我们可以用另一种更直观的方式：
实际上，我们可以将dp_odd[i]理解为“考虑前 i 个元素，且最后一个选中的元素符号为+时的最大交替和”，dp_even[i]为“最后一个选中的元素符号为-时的最大交替和”。如果从未选中过任何元素呢？我们可以把“从未选中”视为一种特殊情况，但为了简化，初始化时：
dp_odd[0] = 0（可以理解为还没有选任何元素时，奇数位置的和为 0？不合适）
更常见做法：
设odd = 0,even = 0作为滚动变量。
对于第一个元素nums[0]：- 作为奇数位置：
odd = max(odd, nums[0])（因为之前 even 为 0，odd 为 0，odd = max(0, 0 + nums[0], nums[0]) = nums[0]）。 - 作为偶数位置：
even = max(even, odd - nums[0])= max(0, nums[0] - nums[0]) = 0。
但这样会漏掉只选第一个元素的情况吗？不会，因为
odd = nums[0]已经包含了只选第一个元素。我们推导一遍递推公式的正确性：
设odd[i]表示从前 i 个元素中选一个子序列，且最后一个元素符号为+的最大交替和。
设even[i]表示从前 i 个元素中选一个子序列，且最后一个元素符号为-的最大交替和。
转移：odd[i] = max(odd[i-1], even[i-1] + nums[i-1], nums[i-1]) even[i] = max(even[i-1], odd[i-1] - nums[i-1])初始化：
odd[0] = even[0] = 0是合理的，因为空序列的交替和为 0，且没有最后一个元素的符号概念。验证：
i=1,nums[0]=4：
odd[1] = max(0, 0 + 4, 4) = 4
even[1] = max(0, 0 - 4) = 0
正确（只选 4 得到 4；选空序列得到 0）。i=2,nums[1]=2：
odd[2] = max(odd[1]=4, even[1]+2=2, 2) = 4
even[2] = max(even[1]=0, odd[1]-2=4-2=2) = 2
解释：偶数位置结尾的最大交替和是 2，对应子序列[4,2]：4 - 2 = 2。i=3,nums[2]=5：
odd[3] = max(odd[2]=4, even[2]+5=2+5=7, 5) = 7
even[3] = max(even[2]=2, odd[2]-5=4-5=-1) = 2
奇数位置结尾最大是 7，对应[4,2,5]：4 - 2 + 5 = 7。i=4,nums[3]=3：
odd[4] = max(7, even[3]+3=2+3=5, 3) = 7
even[4] = max(2, odd[3]-3=7-3=4) = 4
偶数位置结尾最大是 4，对应[4,2,3]：4 - 2 + 3 = 5？等等，[4,2,3]的交替和是 4 - 2 + 3 = 5，但我们的 even[4] 是 4，哪里不对？检查：偶数位置结尾意味着最后一个元素符号是
-，但[4,2,3]最后一个元素 3 符号是+，所以不在 even 中。
那么 even[4]=4 对应什么子序列？
odd[3]-3 = 7-3=4，即[4,2,5,3]：4 - 2 + 5 - 3 = 4，最后一个元素符号是-，正确。
所以 even[4]=4 合理。最终答案应该是
max(odd[4], even[4]) = max(7,4) = 7。 - 作为奇数位置：
第五步：优化空间
由于 odd[i] 和 even[i] 只依赖于前一个状态，我们可以只用两个变量 odd 和 even 滚动更新。
初始化：odd = 0, even = 0
遍历每个数 x：
new_odd = max(odd, even + x, x)
new_even = max(even, odd - x)
odd, even = new_odd, new_even
遍历结束后，答案 = max(odd, even)。
第六步：复杂度分析
- 时间复杂度：O(n)，只需一次遍历。
- 空间复杂度：O(1)，仅用两个变量。
第七步：举例验证
以 nums = [4,2,5,3] 为例：
初始：odd=0, even=0
-
x=4:
new_odd = max(0, 0+4, 4) = 4
new_even = max(0, 0-4) = 0
odd=4, even=0 -
x=2:
new_odd = max(4, 0+2, 2) = 4
new_even = max(0, 4-2) = 2
odd=4, even=2 -
x=5:
new_odd = max(4, 2+5, 5) = 7
new_even = max(2, 4-5) = 2
odd=7, even=2 -
x=3:
new_odd = max(7, 2+3, 3) = 7
new_even = max(2, 7-3) = 4
odd=7, even=4
结果 = max(7,4) = 7 ✅
第八步：为什么这样得到最优解？
本质上是将问题分解为两种结尾符号的状态，通过选择每个元素（或不选）来最大化未来可能的总和。
因为交替和的正负取决于位置，我们保证每次转移都考虑了“以当前元素结尾”和“不以当前元素结尾”两种情况，并且由于动态规划的无后效性（只依赖前一个状态），最终得到全局最优。
最终算法代码（Python风格）：
def maxAlternatingSum(nums):
odd = 0 # 最后符号为+
even = 0 # 最后符号为-
for x in nums:
new_odd = max(odd, even + x, x)
new_even = max(even, odd - x)
odd, even = new_odd, new_even
return max(odd, even)