题目描述
思路解析动画文字版
记牢这两行状态: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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题