题目描述
思路解析
一句话答案：LeetCode 1043 分隔数组以得到最大和：线性 DP，dp[i] 记前 i 个数切好后的最大和，只枚举最后一段切多长（不超过 k）、段内最大值乘长度接上 dp[i-len]。时间 O(n·k)、空间 O(n)。
分隔数组以得到最大和，到底在最大化什么
给整数数组 arr 和上限 k，把 arr 切成若干连续段，每段长度不超过 k，每段的数全换成本段最大值，求换完后总和最大。以 arr=[1,15,7,9,2,5,10]、k 取 3 为例，切成 [1,15,7] [9] [2,5,10]，三段换成 15、9、10，和 15×3 + 9 + 10×3 = 84。段越长最大值被复制越多次，但也可能捆进小数拉低总和。
为什么把所有切法逐一试一遍会炸
n 个数之间有 n-1 条缝，每条缝切或不切，分割方案就有 2^(n-1) 种，是指数级的 O(2ⁿ)（大 O 记号，描述规模变大时操作数怎么涨），根本试不完，前缀还被反复重算。既然『前若干个数的最大和』能独立算一次存下来复用，指数枚举就压成一趟递推（用前面算好的结果推后面的）。
状态为什么只盯前 i 个数、还只管最后一段
动态规划（DP，把『前 i 个数的最大和』算一次存下、后面直接取）这样定状态（状态即要记录的那几个量）：dp[i] 表示 arr 前 i 个数切好后的最大和，答案是 dp[n]。
为什么只盯最后一段：不管前面怎么切，末段总有个长度 len（1 到 k）；定下它是哪几个数，前面就是个更小的同类问题 dp[i-len]。于是 dp[i] 枚举末段切多长，把贡献接到 dp[i-len]，在所有 len 里挑最大。
枚举末段长度时，一段的贡献为什么是最大值乘长度
最后一段是末尾的 len 个数，全换成段内最大值，贡献不是原和，而是段内最大值乘 len。设最大值为 mx，候选和就是 dp[i-len] + mx×len，dp[i] 取最大的候选。len 上限取 min(k, i)：既不超过 k，也不超过只有的 i 个数；段内最大值用 mx = max(mx, arr[i-len]) 边扩边更新。
拿题面示例把这张 dp 表逐格填出来
地基 dp[0]=0。dp[1]=1。dp[2]=30：len=2 段 [1,15] 贡 15×2=30，胜过 len=1 的 16。dp[3]=45：len=3 段 [1,15,7] 贡 45 接 dp[0]，压过 37、31。同法 dp[4]=max(dp[3]+9, dp[2]+9×2, dp[1]+15×3)=54、dp[5]=63、dp[6]=72。dp[7]=84：len=3 段 [2,5,10] 贡 10×3=30 接 dp[4]=54 得 84，胜过 82、83，即答案，对应切法 [1,15,7] [9] [2,5,10]。
末段长度忘跟 i 取小，dp[1] 为什么读到负数格
len 上限只写死成 k、忘跟 i 取 min，填 dp[1] 时 len 会试到 3，dp[i-len] 变成 dp[-2]，Python 里绕到末尾读到错格子，上限必须取 min(k, i)。另一处爱写反：贡献加成原和、没做『整段换最大值』，和会偏小。复杂度：外层 n 格、内层最多 k 种段长，时间 O(n·k)；一维 dp，空间 O(n)。两个边界：上限为 1 时每段一个数、答案即原数组求和；上限大到罩住整数组时整段合一、答案 max(arr) × n。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
一句话套路:dp[i] 只看「最后一段切多长」,前面交给 dp[i-len]。下面逐格填这张 dp 表,套的就是这一条规则。
先看 dp 表。dp[0]=0 是地基:一个元素都不取,和当然是 0。后面每一格都会站在前面的格子上算出来。
轮到 dp[1]（紫色)。它的「最后一段」最多 1 个数,我们把 len 从 1 试到 1,每种切法都算一遍,取最大那个。
试 len=1:最后一段是 [1],段内最大值 1,整段替换后贡献 1*1=1;再加上前面的最优 dp[0]=0(蓝色依赖格),候选总和 1。
候选 1 比目前的 dp[1] 更大,更新 dp[1]=1。
所有 len 试完,dp[1]=1 锁定(变绿)。它代表「前 1 个元素」切好后的最大和,后面的格子可以直接拿来用。
轮到 dp[2]（紫色)。它的「最后一段」最多 2 个数,我们把 len 从 1 试到 2,每种切法都算一遍,取最大那个。
试 len=1:最后一段是 [15],段内最大值 15,整段替换后贡献 15*1=15;再加上前面的最优 dp[1]=1(蓝色依赖格),候选总和 16。
候选 16 比目前的 dp[2] 更大,更新 dp[2]=16。
试 len=2:最后一段是 [1,15],段内最大值 15,整段替换后贡献 15*2=30;再加上前面的最优 dp[0]=0(蓝色依赖格),候选总和 30。
候选 30 比目前的 dp[2] 更大,更新 dp[2]=30。
所有 len 试完,dp[2]=30 锁定(变绿)。它代表「前 2 个元素」切好后的最大和,后面的格子可以直接拿来用。
轮到 dp[3]（紫色)。它的「最后一段」最多 3 个数,我们把 len 从 1 试到 3,每种切法都算一遍,取最大那个。
试 len=1:最后一段是 [7],段内最大值 7,整段替换后贡献 7*1=7;再加上前面的最优 dp[2]=30(蓝色依赖格),候选总和 37。
候选 37 比目前的 dp[3] 更大,更新 dp[3]=37。
试 len=2:最后一段是 [15,7],段内最大值 15,整段替换后贡献 15*2=30;再加上前面的最优 dp[1]=1(蓝色依赖格),候选总和 31。
候选 31 没超过现在的 dp[3]=37,这种切法不划算,保留原值。
试 len=3:最后一段是 [1,15,7],段内最大值 15,整段替换后贡献 15*3=45;再加上前面的最优 dp[0]=0(蓝色依赖格),候选总和 45。
候选 45 比目前的 dp[3] 更大,更新 dp[3]=45。
所有 len 试完,dp[3]=45 锁定(变绿)。它代表「前 3 个元素」切好后的最大和,后面的格子可以直接拿来用。
轮到 dp[4]（紫色)。它的「最后一段」最多 3 个数,我们把 len 从 1 试到 3,每种切法都算一遍,取最大那个。
试 len=1:最后一段是 [9],段内最大值 9,整段替换后贡献 9*1=9;再加上前面的最优 dp[3]=45(蓝色依赖格),候选总和 54。
候选 54 比目前的 dp[4] 更大,更新 dp[4]=54。
试 len=2:最后一段是 [7,9],段内最大值 9,整段替换后贡献 9*2=18;再加上前面的最优 dp[2]=30(蓝色依赖格),候选总和 48。
候选 48 没超过现在的 dp[4]=54,这种切法不划算,保留原值。
试 len=3:最后一段是 [15,7,9],段内最大值 15,整段替换后贡献 15*3=45;再加上前面的最优 dp[1]=1(蓝色依赖格),候选总和 46。
候选 46 没超过现在的 dp[4]=54,这种切法不划算,保留原值。
所有 len 试完,dp[4]=54 锁定(变绿)。它代表「前 4 个元素」切好后的最大和,后面的格子可以直接拿来用。
轮到 dp[5]（紫色)。它的「最后一段」最多 3 个数,我们把 len 从 1 试到 3,每种切法都算一遍,取最大那个。
试 len=1:最后一段是 [2],段内最大值 2,整段替换后贡献 2*1=2;再加上前面的最优 dp[4]=54(蓝色依赖格),候选总和 56。
候选 56 比目前的 dp[5] 更大,更新 dp[5]=56。
试 len=2:最后一段是 [9,2],段内最大值 9,整段替换后贡献 9*2=18;再加上前面的最优 dp[3]=45(蓝色依赖格),候选总和 63。
候选 63 比目前的 dp[5] 更大,更新 dp[5]=63。
试 len=3:最后一段是 [7,9,2],段内最大值 9,整段替换后贡献 9*3=27;再加上前面的最优 dp[2]=30(蓝色依赖格),候选总和 57。
候选 57 没超过现在的 dp[5]=63,这种切法不划算,保留原值。
所有 len 试完,dp[5]=63 锁定(变绿)。它代表「前 5 个元素」切好后的最大和,后面的格子可以直接拿来用。
轮到 dp[6]（紫色)。它的「最后一段」最多 3 个数,我们把 len 从 1 试到 3,每种切法都算一遍,取最大那个。
试 len=1:最后一段是 [5],段内最大值 5,整段替换后贡献 5*1=5;再加上前面的最优 dp[5]=63(蓝色依赖格),候选总和 68。
候选 68 比目前的 dp[6] 更大,更新 dp[6]=68。
试 len=2:最后一段是 [2,5],段内最大值 5,整段替换后贡献 5*2=10;再加上前面的最优 dp[4]=54(蓝色依赖格),候选总和 64。
候选 64 没超过现在的 dp[6]=68,这种切法不划算,保留原值。
试 len=3:最后一段是 [9,2,5],段内最大值 9,整段替换后贡献 9*3=27;再加上前面的最优 dp[3]=45(蓝色依赖格),候选总和 72。
候选 72 比目前的 dp[6] 更大,更新 dp[6]=72。
所有 len 试完,dp[6]=72 锁定(变绿)。它代表「前 6 个元素」切好后的最大和,后面的格子可以直接拿来用。
轮到 dp[7]（紫色)。它的「最后一段」最多 3 个数,我们把 len 从 1 试到 3,每种切法都算一遍,取最大那个。
试 len=1:最后一段是 [10],段内最大值 10,整段替换后贡献 10*1=10;再加上前面的最优 dp[6]=72(蓝色依赖格),候选总和 82。
候选 82 比目前的 dp[7] 更大,更新 dp[7]=82。
试 len=2:最后一段是 [5,10],段内最大值 10,整段替换后贡献 10*2=20;再加上前面的最优 dp[5]=63(蓝色依赖格),候选总和 83。
候选 83 比目前的 dp[7] 更大,更新 dp[7]=83。
试 len=3:最后一段是 [2,5,10],段内最大值 10,整段替换后贡献 10*3=30;再加上前面的最优 dp[4]=54(蓝色依赖格),候选总和 84。
候选 84 比目前的 dp[7] 更大,更新 dp[7]=84。
所有 len 试完,dp[7]=84 锁定(变绿)。它代表「前 7 个元素」切好后的最大和,后面的格子可以直接拿来用。
填到最后一格 dp[7]=84,就是把整个数组切好后能得到的最大总和。对应的一种切法是 [1,15,7] [9] [2,5,10]:15*3 + 9 + 10*3 = 84。
k=1 时退化为原数组求和;k 够大到覆盖整个数组时,可以整段合成一段,最大值会复制 n 次,答案是 max(arr) * n。
两个高频追问:末段拆分的通用性,以及 O(n·k) 的合理性。
参考代码
from typing import Listclass Solution: def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int: n = len(arr) dp = [0] * (n + 1) for i in range(1, n + 1): mx = 0 for length in range(1, min(k, i) + 1): mx = max(mx, arr[i - length]) dp[i] = max(dp[i], dp[i - length] + mx * length) return dp[n]复杂度
- 时间：O(n·k)，每个 dp[i] 枚举最多 k 种段长,共 n 个 i
- 空间：O(n)，一维 dp 数组,长度 n+1
易错点
面试追问把动画讲成自己的话
追问为什么按「最后一段」拆分,而不是「第一段」?
追问能不能优化到比 O(n·k) 更快?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长字符串链
LeetCode 1048 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题