题目描述
思路解析
一句话答案：LeetCode 1186 删除一次得到子数组最大和用两状态动态规划：dp0 记不删的最大和、dp1 记删过一次的最大和，dp1 靠删当前接 dp0 或留当前接 dp1，全程取最大。时间 O(n)、空间 O(1)。
删一个元素，到底在所有子数组里挑什么
给数组 arr，选一段连续子数组，可删掉其中至多一个元素（可删可不删），删完不能空，求其中最大的元素和。答案得兼顾一个都不删、和恰好删一个。arr = [1,-2,0,3] 删掉 -2 得 [1,0,3]、和 4；arr = [1,-2,-2,3] 却别删、选 [3] 更好。
为什么把每个删除位置都试一遍会白算
删哪个元素有 n 种选择（含不删），每定一个还要从头求一遍最大连续子数组和，一层套一层就是 O(n²)（大 O 记号，描述规模变大时运算次数怎么涨），n 到 10^5 就跑不动。慢在每换位置，前面那段最大和都从零重算。
两行 dp 各记什么，dp1 那一维为什么是「删过一次」
开两行 dp，也就是动态规划（以第 i 位结尾、删或不删的最大和记表复用）的表。dp0[i] 记「以第 i 个位置结尾、不删的最大子数组和」，就是经典最大子数组（LeetCode 53 的 Kadane：每步在「接前段」和「另起一段」里挑大）。dp1[i] 在 dp0 上多挂一维「已删过一次」，记「以第 i 个位置结尾、恰好删过一个元素的最大和」。dp0、dp1 是两个状态（状态 = 描述当前一步局面的量），答案是两行里的最大值。
dp1 每格为什么在「删当前」和「留当前」两条里取大
dp0 就是 Kadane 那条老式子。新东西在 dp1 的转移（转移 = 由前一格答案推出当前格的式子）：已删过一次的最大和有两条来路。一是删的正好是当前 arr[i]，删完就退回前一格「还没删」的 dp0[i-1]——等于拿前面不删的一段跳过当前接上；二是当前 arr[i] 留着、删除在更早，接前一格「已删过」的 dp1[i-1] 再加 arr[i]。取大：dp1[i] = max(dp0[i-1], dp1[i-1] + arr[i])。dp1[0] 非法（删完为空），拿极小哨兵（哨兵=比任何真实和都小的不可能标记）兜住、别当 0。
拿 [1,-2,3,-2,4,-1,2] 把两行 dp 填到 8
拿题面演示的 arr = [1,-2,3,-2,4,-1,2] 填一遍。dp0 一路 Kadane 扫出 1、-1、3、1、5、4、6。dp1 逐格取两条来路的大者：dp1[1]=max(1, 非法)=1；dp1[2]=max(-1, 1+3)=4；dp1[3]=max(3, 4-2)=3；dp1[4]=max(1, 3+4)=7；dp1[5]=max(5, 7-1)=6；dp1[6]=max(4, 6+2)=8。两行最大 dp1[6]=8 即答案：删掉 [3,-2,4,-1,2] 中间的 -2、接成 [3,4,-1,2]。
dp1[0] 当成 0，全负数组的答案为什么会凭空变大
dp1[0] 是「一个元素还要删」，删完为空、非法。图省事写成 0 就出事：arr 全为负时答案本该是最大的负数，可 dp1[0]=0 会顺着转移把 0 一路抬上去，答案凭空变大。另一处：dp1「删当前」接 dp0[i-1] 而非 dp1[i-1]，接错就成删两次。两行各扫一遍、每格常数运算，时间 O(n)；每格只用前一格，两个滚动变量（只留最近一格）轮替，空间压到 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这两行: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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题