任意子数组和的绝对值的最大值 图解题解
这道题到底在问什么
- 输入
- nums=[1,-3,2,3,-4]
- 输出
- 5
- 输入
- nums=[2,-5,1,-4,3,-2]
- 输出
- 8
- 输入
- nums=[-4,3,2,-3,1]
- 输出
- 5
最优解：一步一步想明白
- 3记牢一句:子数组和 = 两个前缀和相减,所以答案 = 最大前缀和 maxP 减 最小前缀和 minP。累加器从左扫一遍,顺手追 maxP 和 minP,别漏空前缀 P0 = 0。下面每帧都在套这句。
- 4先看清画面。上面是源数组 nums = [2,-5,1,-4,3,-2],一共 6 个数。右边那张表记的是前缀和序列 P,现在只有一个 P0 = 0,代表「一个数都不加」的空前缀。我们准备一个累加器 prefix,起点是 0,再准备两个记录器 maxP 和 minP,都先等于 0。接下来紫色指针从下标 0 往右一格一格走,每走一格就把当前数加进 prefix,得到新的前缀和记进右表,同时看它有没有刷新最大或最小。先从第 0 位开始。
- 5轮到第 0 位。紫色指针落在源数组下标 0,值是 2。右边表里最后一格 P0 现在是 0,它就是把前 0 个数加起来的前缀和,也是我的累加器此刻的值。接下来只要把当前这个 2 累加进去,就能得到下一个前缀和 P1。
- 6把累加器 0 加上当前的 2,得到新的前缀和 2,把它作为 P1 记进右表最后一行。这个 2 就是「从开头一直加到第 0 位」的总和。它同时也是下一轮的累加器起点。现在还差一步:看看这个新前缀和有没有刷新历史的最大或最小。
- 7拿新前缀和 2 和已记录的最大 maxP、最小 minP 比一比。它比原来的 maxP 还大,于是 maxP 被刷新成 2。此刻答案候选 ans 等于 maxP 减 minP,也就是 2 减 0 = 2。maxP 抬高,意味着找到了一个更靠上的前缀和,未来它减去某个很小的前缀和,差可能更大。源数组这一格标绿表示处理完,继续往右走。
- 8轮到第 1 位。紫色指针落在源数组下标 1,值是 -5。右边表里最后一格 P1 现在是 2,它就是把前 1 个数加起来的前缀和,也是我的累加器此刻的值。接下来只要把当前这个 -5 累加进去,就能得到下一个前缀和 P2。
- 9把累加器 2 加上当前的 -5,得到新的前缀和 -3,把它作为 P2 记进右表最后一行。这个 -3 就是「从开头一直加到第 1 位」的总和。它同时也是下一轮的累加器起点。现在还差一步:看看这个新前缀和有没有刷新历史的最大或最小。
- 10拿新前缀和 -3 和已记录的最大 maxP、最小 minP 比一比。它比原来的 minP 还小,于是 minP 被刷新成 -3。此刻答案候选 ans 等于 maxP 减 minP,也就是 2 减 -3 = 5。minP 压低,意味着找到了一个更靠下的谷底,让某个较大前缀和减去它时,差被拉得更大。源数组这一格标绿表示处理完,继续往右走。
- 11轮到第 2 位。紫色指针落在源数组下标 2,值是 1。右边表里最后一格 P2 现在是 -3,它就是把前 2 个数加起来的前缀和,也是我的累加器此刻的值。接下来只要把当前这个 1 累加进去,就能得到下一个前缀和 P3。
- 12把累加器 -3 加上当前的 1,得到新的前缀和 -2,把它作为 P3 记进右表最后一行。这个 -2 就是「从开头一直加到第 2 位」的总和。它同时也是下一轮的累加器起点。现在还差一步:看看这个新前缀和有没有刷新历史的最大或最小。
- 13拿新前缀和 -2 和已记录的最大 maxP = 2、最小 minP = -3 比一比。它落在两者之间,既没超过最大,也没低于最小,所以 maxP 和 minP 都不动。答案候选 ans 依旧是 2 减 -3 = 5。不是每一步都会刷新极值,但每一步都要比一比才安心。源数组这一格标绿表示处理完,继续往右走。
- 14轮到第 3 位。紫色指针落在源数组下标 3,值是 -4。右边表里最后一格 P3 现在是 -2,它就是把前 3 个数加起来的前缀和,也是我的累加器此刻的值。接下来只要把当前这个 -4 累加进去,就能得到下一个前缀和 P4。
- 15把累加器 -2 加上当前的 -4,得到新的前缀和 -6,把它作为 P4 记进右表最后一行。这个 -6 就是「从开头一直加到第 3 位」的总和。它同时也是下一轮的累加器起点。现在还差一步:看看这个新前缀和有没有刷新历史的最大或最小。
- 16拿新前缀和 -6 和已记录的最大 maxP、最小 minP 比一比。它比原来的 minP 还小,于是 minP 被刷新成 -6。此刻答案候选 ans 等于 maxP 减 minP,也就是 2 减 -6 = 8。minP 压低,意味着找到了一个更靠下的谷底,让某个较大前缀和减去它时,差被拉得更大。源数组这一格标绿表示处理完,继续往右走。
- 17轮到第 4 位。紫色指针落在源数组下标 4,值是 3。右边表里最后一格 P4 现在是 -6,它就是把前 4 个数加起来的前缀和,也是我的累加器此刻的值。接下来只要把当前这个 3 累加进去,就能得到下一个前缀和 P5。
- 18把累加器 -6 加上当前的 3,得到新的前缀和 -3,把它作为 P5 记进右表最后一行。这个 -3 就是「从开头一直加到第 4 位」的总和。它同时也是下一轮的累加器起点。现在还差一步:看看这个新前缀和有没有刷新历史的最大或最小。
- 19拿新前缀和 -3 和已记录的最大 maxP = 2、最小 minP = -6 比一比。它落在两者之间,既没超过最大,也没低于最小,所以 maxP 和 minP 都不动。答案候选 ans 依旧是 2 减 -6 = 8。不是每一步都会刷新极值,但每一步都要比一比才安心。源数组这一格标绿表示处理完,继续往右走。
- 20轮到第 5 位。紫色指针落在源数组下标 5,值是 -2。右边表里最后一格 P5 现在是 -3,它就是把前 5 个数加起来的前缀和,也是我的累加器此刻的值。接下来只要把当前这个 -2 累加进去,就能得到下一个前缀和 P6。
- 21把累加器 -3 加上当前的 -2,得到新的前缀和 -5,把它作为 P6 记进右表最后一行。这个 -5 就是「从开头一直加到第 5 位」的总和。它同时也是下一轮的累加器起点。现在还差一步:看看这个新前缀和有没有刷新历史的最大或最小。
- 22拿新前缀和 -5 和已记录的最大 maxP = 2、最小 minP = -6 比一比。它落在两者之间,既没超过最大,也没低于最小,所以 maxP 和 minP 都不动。答案候选 ans 依旧是 2 减 -6 = 8。不是每一步都会刷新极值,但每一步都要比一比才安心。六个数全部扫完了。
- 23扫完看结果。整条前缀和序列里,最大值 maxP = 2 出现在 P1,最小值 minP = -6 出现在 P4。答案就是 maxP 减 minP = 2 减 -6 = 8。这个差对应的是哪一段?正是位于 P1 和 P4 之间的那几个元素,也就是绿色高亮的子数组 [-5,1,-4]。它的和是 -8,是一段很负的和,取绝对值正好是 8。这说明和的绝对值最大,来自一段特别负的子数组,而不是一段很正的。
- 24回看全程:累加器从空前缀 0 出发,滚出前缀和序列 [0,2,-3,-2,-6,-3,-5]。一路上我们只盯着两个数,见过的最大前缀和 maxP 一路涨到 2,见过的最小前缀和 minP 一路降到 -6。最后把这两个极值一减,2 减 -6 = 8,就是任意子数组和的绝对值最大值。整道题没有嵌套循环,一遍扫描、三个变量,线性时间就搞定。
⚠️ 容易写错的地方
✗ 错：只跑一遍求最大子数组和(单向 Kadane)就当答案,漏了负向
✓ 对：同时追最大前缀和 maxP 和最小前缀和 minP 两个方向,答案取 maxP 减 minP
和的绝对值最大,可能来自一段很正的子数组,也可能来自一段很负的。本例答案 8 就来自和为 -8 的负段 [-5,1,-4]。只追最大会把这段漏掉,必须两个方向都盯
✗ 错：用前缀和时纠结 maxP 的下标一定要在 minP 前面才合法
✓ 对：maxP 减 minP 恒为非负,且必对应某个真实子数组和的绝对值,不用管谁先谁后
若 minP 在前、maxP 在后,这个差就是一段正子数组的和;若 maxP 在前、minP 在后,差就是一段负子数组和的绝对值。两种都是合法子数组,直接相减即可,不必额外判断顺序
✗ 错：忘了把空前缀 P0 = 0 纳入 maxP、minP 的比较
✓ 对：前缀和序列从 0 起步,0 本身也是候选极值
子数组允许为空、空和为 0,答案至少是 0;而且以开头 nums[0] 起步的子数组,它的和要靠减去 P0 = 0 才算得出。漏掉这个 0,遇到「从头开始最优」的情形就会算错
完整代码（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 maxAbsoluteSum(self, nums: List[int]) -> int:
f = g = 0
ans = 0
for x in nums:
f = max(f, 0) + x
g = min(g, 0) + x
ans = max(ans, f, abs(g))
return ansC++
#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:
int maxAbsoluteSum(vector<int>& nums) {
int f = 0, g = 0;
int ans = 0;
for (int& x : nums) {
f = max(f, 0) + x;
g = min(g, 0) + x;
ans = max({ans, f, abs(g)});
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int maxAbsoluteSum(int[] nums) {
int f = 0, g = 0;
int ans = 0;
for (int x : nums) {
f = Math.max(f, 0) + x;
g = Math.min(g, 0) + x;
ans = Math.max(ans, Math.max(f, Math.abs(g)));
}
return ans;
}
}复杂度
时间
O(n)
n 是数组长度。一个指针从左扫到右,每个位置只做一次累加、一次和 maxP、minP 的比较,都是常数操作,总共 n 次,所以是线性的 O(n)。参考代码的 f/g 写法同样是一遍扫描,复杂度一致。对比枚举所有子数组再求和的 O(n^2) 甚至 O(n^3) 笨办法,这套线性扫描优势明显
空间
O(1)
按峰值算。真正的实现只需要几个变量:一个累加器 prefix(或 f、g)、一个 maxP、一个 minP、一个答案 ans,不管数组多长,占用都是常数,所以额外空间 O(1)。动画右边画出整条前缀和序列 P 只是为了让你看清推导过程,算法本身并不需要把它们全存下来,滚动着比就行。三种语言都是 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 任意子数组和的绝对值的最大值 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题为什么能转成「前缀和的最大值减最小值」?本质是什么?+
本质是任意区间和都能用前缀和之差表示。子数组 nums[i..j] 的和等于 P[j+1] 减 P[i],所以所有子数组和的集合,就是所有前缀和两两相减的集合。要让某个差的绝对值最大,自然是让其中一个取到最大前缀和 maxP、另一个取到最小前缀和 minP,它们的差 maxP 减 minP 就是最大绝对值。这个差恒为非负,而且一定对应着某一段真实的连续子数组,所以直接就是答案。
参考代码里的 f 和 g 是什么,和前缀和这套方法什么关系?+
f 维护以当前元素结尾的最大子数组和,g 维护以当前元素结尾的最小子数组和,答案每步取 f、g 的绝对值和已有 ans 里最大的。它其实和前缀和法完全等价:f 相当于当前前缀和减去它之前见过的最小前缀和,抓的是正向能拉多大;g 相当于当前前缀和减去之前最大前缀和,抓的是负向能压多低。一个管正、一个管负,合起来覆盖的正是 maxP 减 minP。两种写法二选一都行,前缀和更直观,f/g 写法更省一点笔墨。
三种语言实现上有什么差别?+
逻辑三家一模一样,都是一遍扫描滚动更新 f、g 和 ans,区别只在语法。Python 最短,直接用内置的 max 和 abs,一行把 ans 更新成 max(ans, f, abs(g))。C++ 用花括号初始化列表写 max({ans, f, abs(g)}),一次比较三个值。Java 没有可变参数的 max,得用 Math.max 嵌套两层,再用 Math.abs 取绝对值。三者都只用常数个 int 变量,时间 O(n)、空间 O(1)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 任意子数组和的绝对值的最大值 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。