分隔数组以得到最大和

一句话套路: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) 的合理性。