题目描述
思路解析
一句话答案：LeetCode 1911 最大子序列交替和：双状态动态规划，g 记加项收尾、f 记减项收尾的最大交替和，加减必须轮流所以两行交叉转移，每个数进表或照抄，答案取 max(f[n],g[n])，时间 O(n)、空间 O(1)。
交替和的加减号，到底跟着哪个下标走
给数组 nums，挑一个子序列（按原顺序跳着选），重新从 0 编号，偶数位相加、奇数位相减叫交替和，求最大值。加减号跟重编号后的位置走：[6,2,1,2,5] 里挑 [6,1,5]，1 原来排第 2 位（原数组也从 0 数），重编号后落到第 1 位成了减项，(6+5)-1=10，与示例二一致。
子序列有 2ⁿ 条，挨条算交替和为什么走不通
每个数选或不选，n 个数就是 2ⁿ 条子序列，几十个数就数不完。而且前面一段怎么选最好，在后面每条分支里被重算，这份成绩不随后面的数改变，存下来复用就是动态规划（本题存「加项或减项收尾」两行成绩，后面的数直接在表上接）。
为什么一行状态记不住，非得拆成 f、g 两行
只记「前 i 个数的最大交替和」推不下去：下一个数该加该减，取决于已选的最后一个是加项还是减项。于是把状态（描述算到哪一步的那组量）按收尾拆成两行：g[i] 记前 i 个数里加项收尾的最大交替和，f[i] 记减项收尾的最大。空前缀 f[0]=g[0]=0 代表一个数都没选，第一个数走 f[0]+x 就能进场当加项。
想让加项进场，为什么必须从 f 行接过来
转移（由上一列推出这一列的式子）每行两条来路：想让当前数 x 当加项，前一个被选的数必须是减项，所以 g[i]=max(f[i-1]+x, g[i-1])，后一项是不选、照抄左边；f 行对称，f[i]=max(g[i-1]-x, f[i-1])。加号行的来源在减号行、反过来也一样，「交替」说的就是这件事。减一个数当下变小，这笔亏存在 f 行里，等大数出现接回加号行就赚回来。
拿示例 [6,2,1,2,5] 把两行表逐列填一遍
f[0]=g[0]=0。来 6：g[1]=max(0+6,0)=6，f[1]=max(0-6,0)=0。来 2：g[2]=max(0+2,6)=6，f[2]=max(6-2,0)=4。来 1：g[3]=max(4+1,6)=6，f[3]=max(6-1,4)=5。来 2：g[4]=max(5+2,6)=7，f[4]=max(6-2,5)=5。来 5：g[5]=max(5+5,7)=10，f[5]=max(7-5,5)=5。
答案 max(f[5],g[5])=10，和示例二对上。倒着追：g[5]=f[4]+5，f[4] 照抄 f[3]，f[3]=g[2]-1，g[2] 照抄 g[1]，即加 6、减 1、加 5，正是子序列 [6,1,5]。
Java 用 int 存交替和，为什么会悄悄得出负数
一遍循环、每个数两次取较大，时间 O(n)（操作次数随数组长度线性涨）；两个 n+1 长的数组占 O(n)，每列只靠上一列，换成两个滚动变量（只留最新一列）可压到 O(1)。交替和能累到十的十次方量级（n 和每个数都能到十万，十万×十万），超出 Java int 约 2.1×10⁹ 的上限就变负数，得用 long，C++ 用 long long，Python 不受限。边界：单个数就返回它本身（g[1] 把它当加项收下）；收尾取 f[n]、g[n] 较大者，本题全是正数、g[n] 不低于 f[n]，只回 g[n] 碰巧也对，按 max 写最稳。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这两行状态:g 是加号收尾、f 是减号收尾。想加就从 f 接过来加,想减就从 g 接过来减,不想动就照抄上一列。下面从空前缀开始,一列一列往右填。
先搭表。上面一行是 g 加结尾,下面一行是 f 减结尾,列头是空加上五个数 6、2、1、2、5。最左边这一列代表空前缀,也就是一个数都还没选,这时候不管说加号收尾还是减号收尾,值都是 0,先把这两格填 0。接下来从左往右,每来一个数就填一列。
轮到第 1 个数 6,先填上面的 g 加结尾这格。想让 6 当加号进来,它前面必须是减号收尾,所以看下面那格 f[0] 等于 0,加上 6 得 6。要是不选 6,就照抄左边的 g[0] 等于 0。两个黄格就是它的两个来源,取较大的那个。
6 和 0 里取较大,g[1] 落子 6。这一步真的把 6 当加号选了进来,加号收尾的成绩涨到了 6。
同一个数 6,再填下面的 f 减结尾这格。想让 6 当减号进来,它前面必须是加号收尾,所以看上面那格 g[0] 等于 0,减去 6 得 -6。要是不选它,就照抄左边的 f[0] 等于 0。还是两个来源取较大。
-6 和 0 里取较大,f[1] 落子 0。减掉 6 反而更亏,不如保留原来的 0,所以这格不动。
轮到第 2 个数 2,先填上面的 g 加结尾这格。想让 2 当加号进来,它前面必须是减号收尾,所以看下面那格 f[1] 等于 0,加上 2 得 2。要是不选 2,就照抄左边的 g[1] 等于 6。两个黄格就是它的两个来源,取较大的那个。
2 和 6 里取较大,g[2] 落子 6。不选 2 更划算,加号收尾的成绩保持在 6 没动。
同一个数 2,再填下面的 f 减结尾这格。想让 2 当减号进来,它前面必须是加号收尾,所以看上面那格 g[1] 等于 6,减去 2 得 4。要是不选它,就照抄左边的 f[1] 等于 0。还是两个来源取较大。
4 和 0 里取较大,f[2] 落子 4。这一步把 2 当减号减掉了,尽管当下变小,却给后面再接一个大加号铺好了路。
轮到第 3 个数 1,先填上面的 g 加结尾这格。想让 1 当加号进来,它前面必须是减号收尾,所以看下面那格 f[2] 等于 4,加上 1 得 5。要是不选 1,就照抄左边的 g[2] 等于 6。两个黄格就是它的两个来源,取较大的那个。
5 和 6 里取较大,g[3] 落子 6。不选 1 更划算,加号收尾的成绩保持在 6 没动。
同一个数 1,再填下面的 f 减结尾这格。想让 1 当减号进来,它前面必须是加号收尾,所以看上面那格 g[2] 等于 6,减去 1 得 5。要是不选它,就照抄左边的 f[2] 等于 4。还是两个来源取较大。
5 和 4 里取较大,f[3] 落子 5。这一步把 1 当减号减掉了,尽管当下变小,却给后面再接一个大加号铺好了路。
轮到第 4 个数 2,先填上面的 g 加结尾这格。想让 2 当加号进来,它前面必须是减号收尾,所以看下面那格 f[3] 等于 5,加上 2 得 7。要是不选 2,就照抄左边的 g[3] 等于 6。两个黄格就是它的两个来源,取较大的那个。
7 和 6 里取较大,g[4] 落子 7。这一步真的把 2 当加号选了进来,加号收尾的成绩涨到了 7。
同一个数 2,再填下面的 f 减结尾这格。想让 2 当减号进来,它前面必须是加号收尾,所以看上面那格 g[3] 等于 6,减去 2 得 4。要是不选它,就照抄左边的 f[3] 等于 5。还是两个来源取较大。
4 和 5 里取较大,f[4] 落子 5。减掉 2 反而更亏,不如保留原来的 5,所以这格不动。
轮到第 5 个数 5,先填上面的 g 加结尾这格。想让 5 当加号进来,它前面必须是减号收尾,所以看下面那格 f[4] 等于 5,加上 5 得 10。要是不选 5,就照抄左边的 g[4] 等于 7。两个黄格就是它的两个来源,取较大的那个。
10 和 7 里取较大,g[5] 落子 10。这一步真的把 5 当加号选了进来,加号收尾的成绩涨到了 10。
同一个数 5,再填下面的 f 减结尾这格。想让 5 当减号进来,它前面必须是加号收尾,所以看上面那格 g[4] 等于 7,减去 5 得 2。要是不选它,就照抄左边的 f[4] 等于 5。还是两个来源取较大。
2 和 5 里取较大,f[5] 落子 5。减掉 5 反而更亏,不如保留原来的 5,所以这格不动。
表填满了。最后一列两格,g[5] 等于 10,f[5] 等于 5。最终答案要在这两个里取较大,因为子序列既可以加号收尾也可以减号收尾。这里 10 更大,所以答案是 10。加号收尾几乎总是更划算,因为最后多加一个正数不会吃亏。
回头看这 10 是哪几个数凑的。g[5] 的 10 来自 f[4] 加 5,f[4] 一路照抄到 f[3] 的减 1,f[3] 的 5 来自 g[2] 减 1,g[2] 照抄到 g[1] 的加 6。串起来就是:先加 6,再减 1,最后加 5,正好对应子序列 [6,1,5],交替和 (6 + 5) - 1 = 10。填表其实就是在悄悄帮我们挑这三个数。
边界想清:单个数就返回它本身、递增时往往只留最大一个数、经典例 [4,2,5,3] 得 7。
面试重点:两状态定义与转移、空间压到 O(1)、可用股票或奇偶长度类比。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maxAlternatingSum(self, nums: List[int]) -> int: n = len(nums) f = [0] * (n + 1) g = [0] * (n + 1) for i, x in enumerate(nums, 1): f[i] = max(g[i - 1] - x, f[i - 1]) g[i] = max(f[i - 1] + x, g[i - 1]) return max(f[n], g[n])复杂度
- 时间：O(n)，n 是数组长度。只从左到右扫一遍,每个数在 f 和 g 两行各做一次取较大、常数操作,总量随 n 线性增长
- 空间：O(n)，本节代码开了两个长度 n 加 1 的数组 f、g,空间随 n 线性增长;又因为每列只依赖上一列的 f[i-1]、g[i-1],可以只留两个滚动变量,把空间进一步压到 O(1)
易错点
面试追问把动画讲成自己的话
追问这题的状态怎么定义、转移怎么来?
追问空间能优化到多少?
追问有没有别的角度理解这两个状态?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
扣分后的最大得分
LeetCode 1937 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题