最大交替子序列和 图解题解
这道题到底在问什么
- 输入
- nums = [4,2,5,3]
- 输出
- 7 最优子序列 [4,2,5] = (4 + 5) - 2 = 7
- 输入
- nums = [6,2,1,2,5]
- 输出
- 10 最优子序列 [6,1,5] = (6 + 5) - 1 = 10
最优解：一步一步想明白
- 3记牢这两行状态:g 是加号收尾、f 是减号收尾。想加就从 f 接过来加,想减就从 g 接过来减,不想动就照抄上一列。下面从空前缀开始,一列一列往右填。
- 4先搭表。上面一行是 g 加结尾,下面一行是 f 减结尾,列头是空加上五个数 6、2、1、2、5。最左边这一列代表空前缀,也就是一个数都还没选,这时候不管说加号收尾还是减号收尾,值都是 0,先把这两格填 0。接下来从左往右,每来一个数就填一列。
- 5轮到第 1 个数 6,先填上面的 g 加结尾这格。想让 6 当加号进来,它前面必须是减号收尾,所以看下面那格 f[0] 等于 0,加上 6 得 6。要是不选 6,就照抄左边的 g[0] 等于 0。两个黄格就是它的两个来源,取较大的那个。
- 66 和 0 里取较大,g[1] 落子 6。这一步真的把 6 当加号选了进来,加号收尾的成绩涨到了 6。
- 7同一个数 6,再填下面的 f 减结尾这格。想让 6 当减号进来,它前面必须是加号收尾,所以看上面那格 g[0] 等于 0,减去 6 得 -6。要是不选它,就照抄左边的 f[0] 等于 0。还是两个来源取较大。
- 8-6 和 0 里取较大,f[1] 落子 0。减掉 6 反而更亏,不如保留原来的 0,所以这格不动。
- 9轮到第 2 个数 2,先填上面的 g 加结尾这格。想让 2 当加号进来,它前面必须是减号收尾,所以看下面那格 f[1] 等于 0,加上 2 得 2。要是不选 2,就照抄左边的 g[1] 等于 6。两个黄格就是它的两个来源,取较大的那个。
- 102 和 6 里取较大,g[2] 落子 6。不选 2 更划算,加号收尾的成绩保持在 6 没动。
- 11同一个数 2,再填下面的 f 减结尾这格。想让 2 当减号进来,它前面必须是加号收尾,所以看上面那格 g[1] 等于 6,减去 2 得 4。要是不选它,就照抄左边的 f[1] 等于 0。还是两个来源取较大。
- 124 和 0 里取较大,f[2] 落子 4。这一步把 2 当减号减掉了,尽管当下变小,却给后面再接一个大加号铺好了路。
- 13轮到第 3 个数 1,先填上面的 g 加结尾这格。想让 1 当加号进来,它前面必须是减号收尾,所以看下面那格 f[2] 等于 4,加上 1 得 5。要是不选 1,就照抄左边的 g[2] 等于 6。两个黄格就是它的两个来源,取较大的那个。
- 145 和 6 里取较大,g[3] 落子 6。不选 1 更划算,加号收尾的成绩保持在 6 没动。
- 15同一个数 1,再填下面的 f 减结尾这格。想让 1 当减号进来,它前面必须是加号收尾,所以看上面那格 g[2] 等于 6,减去 1 得 5。要是不选它,就照抄左边的 f[2] 等于 4。还是两个来源取较大。
- 165 和 4 里取较大,f[3] 落子 5。这一步把 1 当减号减掉了,尽管当下变小,却给后面再接一个大加号铺好了路。
- 17轮到第 4 个数 2,先填上面的 g 加结尾这格。想让 2 当加号进来,它前面必须是减号收尾,所以看下面那格 f[3] 等于 5,加上 2 得 7。要是不选 2,就照抄左边的 g[3] 等于 6。两个黄格就是它的两个来源,取较大的那个。
- 187 和 6 里取较大,g[4] 落子 7。这一步真的把 2 当加号选了进来,加号收尾的成绩涨到了 7。
- 19同一个数 2,再填下面的 f 减结尾这格。想让 2 当减号进来,它前面必须是加号收尾,所以看上面那格 g[3] 等于 6,减去 2 得 4。要是不选它,就照抄左边的 f[3] 等于 5。还是两个来源取较大。
- 204 和 5 里取较大,f[4] 落子 5。减掉 2 反而更亏,不如保留原来的 5,所以这格不动。
- 21轮到第 5 个数 5,先填上面的 g 加结尾这格。想让 5 当加号进来,它前面必须是减号收尾,所以看下面那格 f[4] 等于 5,加上 5 得 10。要是不选 5,就照抄左边的 g[4] 等于 7。两个黄格就是它的两个来源,取较大的那个。
- 2210 和 7 里取较大,g[5] 落子 10。这一步真的把 5 当加号选了进来,加号收尾的成绩涨到了 10。
- 23同一个数 5,再填下面的 f 减结尾这格。想让 5 当减号进来,它前面必须是加号收尾,所以看上面那格 g[4] 等于 7,减去 5 得 2。要是不选它,就照抄左边的 f[4] 等于 5。还是两个来源取较大。
- 242 和 5 里取较大,f[5] 落子 5。减掉 5 反而更亏,不如保留原来的 5,所以这格不动。
- 25表填满了。最后一列两格,g[5] 等于 10,f[5] 等于 5。最终答案要在这两个里取较大,因为子序列既可以加号收尾也可以减号收尾。这里 10 更大,所以答案是 10。加号收尾几乎总是更划算,因为最后多加一个正数不会吃亏。
- 26回头看这 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。填表其实就是在悄悄帮我们挑这三个数。
⚠️ 容易写错的地方
✗ 错：以为要枚举所有子序列再算交替和
✓ 对：用 f、g 两状态一趟线性 DP
子序列有指数多个,枚举会超时;只跟踪加号收尾和减号收尾两种最优,每个数常数时间决策即可
✗ 错：把结果一直存进 int
✓ 对：Java 用 long、C plus plus 用 long long
数组最长十的五次方、每个数最大十的五次方,交替和量级到十的十次方,超出 int 上限会溢出成负数
✗ 错：以为返回 g[n] 会漏掉减号收尾可能更优的解
✓ 对：正数约束下 g[n] 恒不小于 f[n],返回 g[n] 与取 max 等价,这里统一取 max 保持两状态对称
nums 每个数都是正数,任何减号收尾的子序列删掉最后一个被减的正数都会更大,所以最优解必以加号收尾;取 max 只是口径统一、更保守
✗ 错：算 g[i] 时用了本列刚更新的 f[i]
✓ 对：f[i] 和 g[i] 都只依赖上一列 i-1
两个转移读的都是 f[i-1]、g[i-1],若误用本列新值会把还没成立的状态提前算进去,结果偏大
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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])C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
long long maxAlternatingSum(vector<int>& nums) {
int n = nums.size();
vector<long long> f(n + 1), g(n + 1);
for (int i = 1; i <= n; ++i) {
f[i] = max(g[i - 1] - nums[i - 1], f[i - 1]);
g[i] = max(f[i - 1] + nums[i - 1], g[i - 1]);
}
return max(f[n], g[n]);
}
};Java
import java.util.*;
class Solution {
public long maxAlternatingSum(int[] nums) {
int n = nums.length;
long[] f = new long[n + 1];
long[] g = new long[n + 1];
for (int i = 1; i <= n; ++i) {
f[i] = Math.max(g[i - 1] - nums[i - 1], f[i - 1]);
g[i] = Math.max(f[i - 1] + nums[i - 1], g[i - 1]);
}
return Math.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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大交替子序列和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的状态怎么定义、转移怎么来?+
定义两个状态:g[i] 是前 i 个数里以加号收尾的最大交替和,f[i] 是以减号收尾或为空的最大交替和。因为加减必须交替,新数想当加号就得接在减号收尾后面,g[i] = max(f[i-1] + nums[i-1], g[i-1]);想当减号就接在加号收尾后面,f[i] = max(g[i-1] - nums[i-1], f[i-1]);两式的第二项都是不选当前数 nums[i-1](也就是第 i 个数)。初值 f[0]=g[0]=0,答案是 max(f[n], g[n])。
空间能优化到多少?+
能压到 O(1)。转移只用到上一列的 f[i-1] 和 g[i-1],所以不必开整张表,只留两个滚动变量,边遍历边更新即可。注意更新时要用旧的 f、g 同时算出新的 f、g,别让本轮更新互相污染。时间仍是 O(n)。
有没有别的角度理解这两个状态?+
可以类比买卖股票:g 相当于手里持有收益、f 相当于空仓,加一个数像买入的反向、减一个数像卖出,交替进行。也可以直接说 g 是子序列长度为奇数、f 是长度为偶数或空。不同说法本质是同一组转移,面试时讲清加减交替这层就够了。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最大交替子序列和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。