题目描述
思路解析动画文字版
记住这两行:dp0 是不删的最大子数组,dp1 在它基础上多一维「已经删过一次」,dp1 要么删掉当前元素接 dp0,要么保留当前元素接 dp1。
总览 · 两行 dp 表,上行不删、下行删一次：这是一张两行七列的 dp 表。上面一行 dp0 记「以这个位置结尾、一个都没删」的最大子数组和,下面一行 dp1 记「以这个位置结尾、已经删过一次」的最大和。列号 0 到 6 对应数组的每个位置。我们从左往右一列一列填,每填好一列就拿这两格去刷新全局答案。最终答案不是某个固定格子,而是整张表里所有数的最大值。
第 0 列 · 打地基：先填第 0 列,也就是只看第一个数 1。不删的话,以它结尾的最大和就是它自己,dp0[0] = 1。删一次呢?这一段只有它一个元素,删掉就剩空了,题目不允许,所以 dp1[0] 是非法的,用一个极小的哨兵值占位,画面里用空集符号表示。答案先初始化成 dp0[0] = 1。
第 1 列 · 先算不删的 dp0：来到第 1 列,当前数是 -2。先算不删的 dp0:要么把它接到前一格那段后面,得 dp0[0] + -2 = 1 + -2 = -1;要么从它自己重新起一段,得 -2。两者取大,dp0[1] = -1。前面那段还能带来正贡献,接上更好。
第 1 列 · 再算删一次的 dp1：再算删过一次的 dp1。两个来源:第一,把当前的 -2 删掉,那这段就退回到前一格不删的 dp0[0] = 1;第二,保留当前的 -2,说明删除发生在更早,接前一格已删的 dp1[0],也就是 非法。前一格的 dp1 还非法,所以只能走第一种、删掉当前元素。dp1[1] = 1,赢家是「删掉当前的 -2」。
第 1 列 · 结算答案：这一列两格都算好了,拿它们去刷新全局答案。原来的 ans 是 1,和 dp0[1] = -1、dp1[1] = 1 一起取最大,得 1。没有超过之前的 1,答案保持不变。
第 2 列 · 先算不删的 dp0：来到第 2 列,当前数是 3。先算不删的 dp0:要么把它接到前一格那段后面,得 dp0[1] + 3 = -1 + 3 = 2;要么从它自己重新起一段,得 3。两者取大,dp0[2] = 3。前面那段是个累赘,丢掉、从当前位置重开更好。
第 2 列 · 再算删一次的 dp1：再算删过一次的 dp1。两个来源:第一,把当前的 3 删掉,那这段就退回到前一格不删的 dp0[1] = -1;第二,保留当前的 3,说明删除发生在更早,接前一格已删的 dp1[1],也就是 1 + 3 = 4。两者取大。dp1[2] = 4,赢家是「保留 3、删在更早处」。
第 2 列 · 结算答案：这一列两格都算好了,拿它们去刷新全局答案。原来的 ans 是 1,和 dp0[2] = 3、dp1[2] = 4 一起取最大,得 4。比之前更大,答案被刷新成 4。
第 3 列 · 先算不删的 dp0：来到第 3 列,当前数是 -2。先算不删的 dp0:要么把它接到前一格那段后面,得 dp0[2] + -2 = 3 + -2 = 1;要么从它自己重新起一段,得 -2。两者取大,dp0[3] = 1。前面那段还能带来正贡献,接上更好。
第 3 列 · 再算删一次的 dp1：再算删过一次的 dp1。两个来源:第一,把当前的 -2 删掉,那这段就退回到前一格不删的 dp0[2] = 3;第二,保留当前的 -2,说明删除发生在更早,接前一格已删的 dp1[2],也就是 4 + -2 = 2。两者取大。dp1[3] = 3,赢家是「删掉当前的 -2」。
第 3 列 · 结算答案：这一列两格都算好了,拿它们去刷新全局答案。原来的 ans 是 4,和 dp0[3] = 1、dp1[3] = 3 一起取最大,得 4。没有超过之前的 4,答案保持不变。
第 4 列 · 先算不删的 dp0：来到第 4 列,当前数是 4。先算不删的 dp0:要么把它接到前一格那段后面,得 dp0[3] + 4 = 1 + 4 = 5;要么从它自己重新起一段,得 4。两者取大,dp0[4] = 5。前面那段还能带来正贡献,接上更好。
第 4 列 · 再算删一次的 dp1：再算删过一次的 dp1。两个来源:第一,把当前的 4 删掉,那这段就退回到前一格不删的 dp0[3] = 1;第二,保留当前的 4,说明删除发生在更早,接前一格已删的 dp1[3],也就是 3 + 4 = 7。两者取大。dp1[4] = 7,赢家是「保留 4、删在更早处」。
第 4 列 · 结算答案：这一列两格都算好了,拿它们去刷新全局答案。原来的 ans 是 4,和 dp0[4] = 5、dp1[4] = 7 一起取最大,得 7。比之前更大,答案被刷新成 7。
第 5 列 · 先算不删的 dp0：来到第 5 列,当前数是 -1。先算不删的 dp0:要么把它接到前一格那段后面,得 dp0[4] + -1 = 5 + -1 = 4;要么从它自己重新起一段,得 -1。两者取大,dp0[5] = 4。前面那段还能带来正贡献,接上更好。
第 5 列 · 再算删一次的 dp1：再算删过一次的 dp1。两个来源:第一,把当前的 -1 删掉,那这段就退回到前一格不删的 dp0[4] = 5;第二,保留当前的 -1,说明删除发生在更早,接前一格已删的 dp1[4],也就是 7 + -1 = 6。两者取大。dp1[5] = 6,赢家是「保留 -1、删在更早处」。
第 5 列 · 结算答案：这一列两格都算好了,拿它们去刷新全局答案。原来的 ans 是 7,和 dp0[5] = 4、dp1[5] = 6 一起取最大,得 7。没有超过之前的 7,答案保持不变。
第 6 列 · 先算不删的 dp0：来到第 6 列,当前数是 2。先算不删的 dp0:要么把它接到前一格那段后面,得 dp0[5] + 2 = 4 + 2 = 6;要么从它自己重新起一段,得 2。两者取大,dp0[6] = 6。前面那段还能带来正贡献,接上更好。
第 6 列 · 再算删一次的 dp1：再算删过一次的 dp1。两个来源:第一,把当前的 2 删掉,那这段就退回到前一格不删的 dp0[5] = 4;第二,保留当前的 2,说明删除发生在更早,接前一格已删的 dp1[5],也就是 6 + 2 = 8。两者取大。dp1[6] = 8,赢家是「保留 2、删在更早处」。
第 6 列 · 结算答案：这一列两格都算好了,拿它们去刷新全局答案。原来的 ans 是 7,和 dp0[6] = 6、dp1[6] = 8 一起取最大,得 8。比之前更大,答案被刷新成 8。
完成 · 答案 8：整张表填满了,所有 dp0、dp1 里最大的是 dp1[6] = 8,这就是答案 8。顺着它倒推:它来自保留末尾的 2、再往前一路保留,删除其实发生在那个 -2 上,把原来的 [3,-2,4,-1,2] 删掉中间的 -2,接成 [3,4,-1,2],和正好是 8。一个负数卡在两段正数中间,删掉它把左右接通,这就是删除带来的收益。
三个边界都能手验:可删时 dp1 接通左右、全负时答案为负、有时不删反而最优。
面试三连:两状态 dp0/dp1 加转移;空间可滚动到 O(1);它是最大子数组 lc53 加了一维「是否删过」的升级版。
参考代码
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 maximumSum(self, arr: List[int]) -> int: n = len(arr) left = [0] * n right = [0] * n s = 0 for i, x in enumerate(arr): s = max(s, 0) + x left[i] = s s = 0 for i in range(n - 1, -1, -1): s = max(s, 0) + arr[i] right[i] = s ans = max(left) for i in range(1, n - 1): ans = max(ans, left[i - 1] + right[i + 1]) return ans复杂度
- 时间：O(n)，不管是动画的一遍两状态扫,还是参考代码的正向、反向、枚举删除位三遍线性扫,都只跟数组长度成正比,n 到 10^5 也轻松
- 空间：O(n)，按峰值算:参考代码开了 left 和 right 两个长度 n 的数组,所以是 O(n)。两状态 DP 因为每格只依赖前一格,可以只留两个滚动变量压到 O(1)
易错点
面试追问把动画讲成自己的话
追问状态怎么设,转移是什么?
追问能不能把空间压到 O(1)?
追问这题和普通的最大子数组 lc53 是什么关系?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长定差子序列
LeetCode 1218 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题