题目描述
思路解析动画文字版
记牢一句:子数组和 = 两个前缀和相减,所以答案 = 最大前缀和 maxP 减 最小前缀和 minP。累加器从左扫一遍,顺手追 maxP 和 minP,别漏空前缀 P0 = 0。下面每帧都在套这句。
总览 · 前缀和从空前缀 P0 = 0 起步：先看清画面。上面是源数组 nums = [2,-5,1,-4,3,-2],一共 6 个数。右边那张表记的是前缀和序列 P,现在只有一个 P0 = 0,代表「一个数都不加」的空前缀。我们准备一个累加器 prefix,起点是 0,再准备两个记录器 maxP 和 minP,都先等于 0。接下来紫色指针从下标 0 往右一格一格走,每走一格就把当前数加进 prefix,得到新的前缀和记进右表,同时看它有没有刷新最大或最小。先从第 0 位开始。
第 0 位 · 读取 nums[0] = 2：轮到第 0 位。紫色指针落在源数组下标 0,值是 2。右边表里最后一格 P0 现在是 0,它就是把前 0 个数加起来的前缀和,也是我的累加器此刻的值。接下来只要把当前这个 2 累加进去,就能得到下一个前缀和 P1。
第 0 位 · 累加得 P1 = 2：把累加器 0 加上当前的 2,得到新的前缀和 2,把它作为 P1 记进右表最后一行。这个 2 就是「从开头一直加到第 0 位」的总和。它同时也是下一轮的累加器起点。现在还差一步:看看这个新前缀和有没有刷新历史的最大或最小。
第 0 位 · 追踪极值 · maxP = 2 · minP = 0 · ans = maxP 减 minP = 2：拿新前缀和 2 和已记录的最大 maxP、最小 minP 比一比。它比原来的 maxP 还大,于是 maxP 被刷新成 2。此刻答案候选 ans 等于 maxP 减 minP,也就是 2 减 0 = 2。maxP 抬高,意味着找到了一个更靠上的前缀和,未来它减去某个很小的前缀和,差可能更大。源数组这一格标绿表示处理完,继续往右走。
第 1 位 · 读取 nums[1] = -5：轮到第 1 位。紫色指针落在源数组下标 1,值是 -5。右边表里最后一格 P1 现在是 2,它就是把前 1 个数加起来的前缀和,也是我的累加器此刻的值。接下来只要把当前这个 -5 累加进去,就能得到下一个前缀和 P2。
第 1 位 · 累加得 P2 = -3：把累加器 2 加上当前的 -5,得到新的前缀和 -3,把它作为 P2 记进右表最后一行。这个 -3 就是「从开头一直加到第 1 位」的总和。它同时也是下一轮的累加器起点。现在还差一步:看看这个新前缀和有没有刷新历史的最大或最小。
第 1 位 · 追踪极值 · maxP = 2 · minP = -3 · ans = maxP 减 minP = 5：拿新前缀和 -3 和已记录的最大 maxP、最小 minP 比一比。它比原来的 minP 还小,于是 minP 被刷新成 -3。此刻答案候选 ans 等于 maxP 减 minP,也就是 2 减 -3 = 5。minP 压低,意味着找到了一个更靠下的谷底,让某个较大前缀和减去它时,差被拉得更大。源数组这一格标绿表示处理完,继续往右走。
第 2 位 · 读取 nums[2] = 1：轮到第 2 位。紫色指针落在源数组下标 2,值是 1。右边表里最后一格 P2 现在是 -3,它就是把前 2 个数加起来的前缀和,也是我的累加器此刻的值。接下来只要把当前这个 1 累加进去,就能得到下一个前缀和 P3。
第 2 位 · 累加得 P3 = -2：把累加器 -3 加上当前的 1,得到新的前缀和 -2,把它作为 P3 记进右表最后一行。这个 -2 就是「从开头一直加到第 2 位」的总和。它同时也是下一轮的累加器起点。现在还差一步:看看这个新前缀和有没有刷新历史的最大或最小。
第 2 位 · 追踪极值 · maxP = 2 · minP = -3 · ans = maxP 减 minP = 5：拿新前缀和 -2 和已记录的最大 maxP = 2、最小 minP = -3 比一比。它落在两者之间,既没超过最大,也没低于最小,所以 maxP 和 minP 都不动。答案候选 ans 依旧是 2 减 -3 = 5。不是每一步都会刷新极值,但每一步都要比一比才安心。源数组这一格标绿表示处理完,继续往右走。
第 3 位 · 读取 nums[3] = -4：轮到第 3 位。紫色指针落在源数组下标 3,值是 -4。右边表里最后一格 P3 现在是 -2,它就是把前 3 个数加起来的前缀和,也是我的累加器此刻的值。接下来只要把当前这个 -4 累加进去,就能得到下一个前缀和 P4。
第 3 位 · 累加得 P4 = -6：把累加器 -2 加上当前的 -4,得到新的前缀和 -6,把它作为 P4 记进右表最后一行。这个 -6 就是「从开头一直加到第 3 位」的总和。它同时也是下一轮的累加器起点。现在还差一步:看看这个新前缀和有没有刷新历史的最大或最小。
第 3 位 · 追踪极值 · maxP = 2 · minP = -6 · ans = maxP 减 minP = 8：拿新前缀和 -6 和已记录的最大 maxP、最小 minP 比一比。它比原来的 minP 还小,于是 minP 被刷新成 -6。此刻答案候选 ans 等于 maxP 减 minP,也就是 2 减 -6 = 8。minP 压低,意味着找到了一个更靠下的谷底,让某个较大前缀和减去它时,差被拉得更大。源数组这一格标绿表示处理完,继续往右走。
第 4 位 · 读取 nums[4] = 3：轮到第 4 位。紫色指针落在源数组下标 4,值是 3。右边表里最后一格 P4 现在是 -6,它就是把前 4 个数加起来的前缀和,也是我的累加器此刻的值。接下来只要把当前这个 3 累加进去,就能得到下一个前缀和 P5。
第 4 位 · 累加得 P5 = -3：把累加器 -6 加上当前的 3,得到新的前缀和 -3,把它作为 P5 记进右表最后一行。这个 -3 就是「从开头一直加到第 4 位」的总和。它同时也是下一轮的累加器起点。现在还差一步:看看这个新前缀和有没有刷新历史的最大或最小。
第 4 位 · 追踪极值 · maxP = 2 · minP = -6 · ans = maxP 减 minP = 8：拿新前缀和 -3 和已记录的最大 maxP = 2、最小 minP = -6 比一比。它落在两者之间,既没超过最大,也没低于最小,所以 maxP 和 minP 都不动。答案候选 ans 依旧是 2 减 -6 = 8。不是每一步都会刷新极值,但每一步都要比一比才安心。源数组这一格标绿表示处理完,继续往右走。
第 5 位 · 读取 nums[5] = -2：轮到第 5 位。紫色指针落在源数组下标 5,值是 -2。右边表里最后一格 P5 现在是 -3,它就是把前 5 个数加起来的前缀和,也是我的累加器此刻的值。接下来只要把当前这个 -2 累加进去,就能得到下一个前缀和 P6。
第 5 位 · 累加得 P6 = -5：把累加器 -3 加上当前的 -2,得到新的前缀和 -5,把它作为 P6 记进右表最后一行。这个 -5 就是「从开头一直加到第 5 位」的总和。它同时也是下一轮的累加器起点。现在还差一步:看看这个新前缀和有没有刷新历史的最大或最小。
第 5 位 · 追踪极值 · maxP = 2 · minP = -6 · ans = maxP 减 minP = 8：拿新前缀和 -5 和已记录的最大 maxP = 2、最小 minP = -6 比一比。它落在两者之间,既没超过最大,也没低于最小,所以 maxP 和 minP 都不动。答案候选 ans 依旧是 2 减 -6 = 8。不是每一步都会刷新极值,但每一步都要比一比才安心。六个数全部扫完了。
答案定位 · 子数组 [-5,1,-4] 绝对值 8：扫完看结果。整条前缀和序列里,最大值 maxP = 2 出现在 P1,最小值 minP = -6 出现在 P4。答案就是 maxP 减 minP = 2 减 -6 = 8。这个差对应的是哪一段?正是位于 P1 和 P4 之间的那几个元素,也就是绿色高亮的子数组 [-5,1,-4]。它的和是 -8,是一段很负的和,取绝对值正好是 8。这说明和的绝对值最大,来自一段特别负的子数组,而不是一段很正的。
完成 · 最大绝对值 = 8：回看全程:累加器从空前缀 0 出发,滚出前缀和序列 [0,2,-3,-2,-6,-3,-5]。一路上我们只盯着两个数,见过的最大前缀和 maxP 一路涨到 2,见过的最小前缀和 minP 一路降到 -6。最后把这两个极值一减,2 减 -6 = 8,就是任意子数组和的绝对值最大值。整道题没有嵌套循环,一遍扫描、三个变量,线性时间就搞定。
边界:单个正数答案是它自己;单个负数取绝对值(靠空前缀 0 兜底);一串前段很负时,答案来自最负的一段、maxP 恰好是空前缀 0。
面试重点:区间和 = 前缀和之差,故答案 = maxP 减 minP;参考代码的 f/g 是等价写法(正向最大加负向最小);三语言差别只在 max 的写法。
参考代码
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 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 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)
易错点
面试追问把动画讲成自己的话
追问这题为什么能转成「前缀和的最大值减最小值」?本质是什么?
追问参考代码里的 f 和 g 是什么,和前缀和这套方法什么关系?
追问三种语言实现上有什么差别?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最少侧跳次数
LeetCode 1824 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题