分隔数组以得到最大和 图解题解

这道题到底在问什么

输入

arr=[1,15,7,9,2,5,10], k=3

输出

84 （一种切法 [1,15,7] [9] [2,5,10]：15*3 + 9 + 10*3 = 84）

输入

arr=[1], k=1

输出

1 （只有一个数,自成一段）

最优解：一步一步想明白

1. 3一句话套路:dp[i] 只看「最后一段切多长」,前面交给 dp[i-len]。下面逐格填这张 dp 表,套的就是这一条规则。
2. 4先看 dp 表。dp[0]=0 是地基:一个元素都不取,和当然是 0。后面每一格都会站在前面的格子上算出来。
3. 5轮到 dp[1]（紫色)。它的「最后一段」最多 1 个数,我们把 len 从 1 试到 1,每种切法都算一遍,取最大那个。
4. 6试 len=1:最后一段是 [1],段内最大值 1,整段替换后贡献 1*1=1;再加上前面的最优 dp[0]=0(蓝色依赖格),候选总和 1。
5. 7候选 1 比目前的 dp[1] 更大,更新 dp[1]=1。
6. 8所有 len 试完,dp[1]=1 锁定(变绿)。它代表「前 1 个元素」切好后的最大和,后面的格子可以直接拿来用。
7. 9轮到 dp[2]（紫色)。它的「最后一段」最多 2 个数,我们把 len 从 1 试到 2,每种切法都算一遍,取最大那个。
8. 10试 len=1:最后一段是 [15],段内最大值 15,整段替换后贡献 15*1=15;再加上前面的最优 dp[1]=1(蓝色依赖格),候选总和 16。
9. 11候选 16 比目前的 dp[2] 更大,更新 dp[2]=16。
10. 12试 len=2:最后一段是 [1,15],段内最大值 15,整段替换后贡献 15*2=30;再加上前面的最优 dp[0]=0(蓝色依赖格),候选总和 30。
11. 13候选 30 比目前的 dp[2] 更大,更新 dp[2]=30。
12. 14所有 len 试完,dp[2]=30 锁定(变绿)。它代表「前 2 个元素」切好后的最大和,后面的格子可以直接拿来用。
13. 15轮到 dp[3]（紫色)。它的「最后一段」最多 3 个数,我们把 len 从 1 试到 3,每种切法都算一遍,取最大那个。
14. 16试 len=1:最后一段是 [7],段内最大值 7,整段替换后贡献 7*1=7;再加上前面的最优 dp[2]=30(蓝色依赖格),候选总和 37。
15. 17候选 37 比目前的 dp[3] 更大,更新 dp[3]=37。
16. 18试 len=2:最后一段是 [15,7],段内最大值 15,整段替换后贡献 15*2=30;再加上前面的最优 dp[1]=1(蓝色依赖格),候选总和 31。
17. 19候选 31 没超过现在的 dp[3]=37,这种切法不划算,保留原值。
18. 20试 len=3:最后一段是 [1,15,7],段内最大值 15,整段替换后贡献 15*3=45;再加上前面的最优 dp[0]=0(蓝色依赖格),候选总和 45。
19. 21候选 45 比目前的 dp[3] 更大,更新 dp[3]=45。
20. 22所有 len 试完,dp[3]=45 锁定(变绿)。它代表「前 3 个元素」切好后的最大和,后面的格子可以直接拿来用。
21. 23轮到 dp[4]（紫色)。它的「最后一段」最多 3 个数,我们把 len 从 1 试到 3,每种切法都算一遍,取最大那个。
22. 24试 len=1:最后一段是 [9],段内最大值 9,整段替换后贡献 9*1=9;再加上前面的最优 dp[3]=45(蓝色依赖格),候选总和 54。
23. 25候选 54 比目前的 dp[4] 更大,更新 dp[4]=54。
24. 26试 len=2:最后一段是 [7,9],段内最大值 9,整段替换后贡献 9*2=18;再加上前面的最优 dp[2]=30(蓝色依赖格),候选总和 48。
25. 27候选 48 没超过现在的 dp[4]=54,这种切法不划算,保留原值。
26. 28试 len=3:最后一段是 [15,7,9],段内最大值 15,整段替换后贡献 15*3=45;再加上前面的最优 dp[1]=1(蓝色依赖格),候选总和 46。
27. 29候选 46 没超过现在的 dp[4]=54,这种切法不划算,保留原值。
28. 30所有 len 试完,dp[4]=54 锁定(变绿)。它代表「前 4 个元素」切好后的最大和,后面的格子可以直接拿来用。
29. 31轮到 dp[5]（紫色)。它的「最后一段」最多 3 个数,我们把 len 从 1 试到 3,每种切法都算一遍,取最大那个。
30. 32试 len=1:最后一段是 [2],段内最大值 2,整段替换后贡献 2*1=2;再加上前面的最优 dp[4]=54(蓝色依赖格),候选总和 56。
31. 33候选 56 比目前的 dp[5] 更大,更新 dp[5]=56。
32. 34试 len=2:最后一段是 [9,2],段内最大值 9,整段替换后贡献 9*2=18;再加上前面的最优 dp[3]=45(蓝色依赖格),候选总和 63。
33. 35候选 63 比目前的 dp[5] 更大,更新 dp[5]=63。
34. 36试 len=3:最后一段是 [7,9,2],段内最大值 9,整段替换后贡献 9*3=27;再加上前面的最优 dp[2]=30(蓝色依赖格),候选总和 57。
35. 37候选 57 没超过现在的 dp[5]=63,这种切法不划算,保留原值。
36. 38所有 len 试完,dp[5]=63 锁定(变绿)。它代表「前 5 个元素」切好后的最大和,后面的格子可以直接拿来用。
37. 39轮到 dp[6]（紫色)。它的「最后一段」最多 3 个数,我们把 len 从 1 试到 3,每种切法都算一遍,取最大那个。
38. 40试 len=1:最后一段是 [5],段内最大值 5,整段替换后贡献 5*1=5;再加上前面的最优 dp[5]=63(蓝色依赖格),候选总和 68。
39. 41候选 68 比目前的 dp[6] 更大,更新 dp[6]=68。
40. 42试 len=2:最后一段是 [2,5],段内最大值 5,整段替换后贡献 5*2=10;再加上前面的最优 dp[4]=54(蓝色依赖格),候选总和 64。
41. 43候选 64 没超过现在的 dp[6]=68,这种切法不划算,保留原值。
42. 44试 len=3:最后一段是 [9,2,5],段内最大值 9,整段替换后贡献 9*3=27;再加上前面的最优 dp[3]=45(蓝色依赖格),候选总和 72。
43. 45候选 72 比目前的 dp[6] 更大,更新 dp[6]=72。
44. 46所有 len 试完,dp[6]=72 锁定(变绿)。它代表「前 6 个元素」切好后的最大和,后面的格子可以直接拿来用。
45. 47轮到 dp[7]（紫色)。它的「最后一段」最多 3 个数,我们把 len 从 1 试到 3,每种切法都算一遍,取最大那个。
46. 48试 len=1:最后一段是 [10],段内最大值 10,整段替换后贡献 10*1=10;再加上前面的最优 dp[6]=72(蓝色依赖格),候选总和 82。
47. 49候选 82 比目前的 dp[7] 更大,更新 dp[7]=82。
48. 50试 len=2:最后一段是 [5,10],段内最大值 10,整段替换后贡献 10*2=20;再加上前面的最优 dp[5]=63(蓝色依赖格),候选总和 83。
49. 51候选 83 比目前的 dp[7] 更大,更新 dp[7]=83。
50. 52试 len=3:最后一段是 [2,5,10],段内最大值 10,整段替换后贡献 10*3=30;再加上前面的最优 dp[4]=54(蓝色依赖格),候选总和 84。
51. 53候选 84 比目前的 dp[7] 更大,更新 dp[7]=84。
52. 54所有 len 试完,dp[7]=84 锁定(变绿)。它代表「前 7 个元素」切好后的最大和,后面的格子可以直接拿来用。
53. 55填到最后一格 dp[7]=84,就是把整个数组切好后能得到的最大总和。对应的一种切法是 [1,15,7] [9] [2,5,10]:15*3 + 9 + 10*3 = 84。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class 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]

#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; ++i) {
            int mx = 0;
            for (int len = 1; len <= min(k, i); ++len) {
                mx = max(mx, arr[i-len]);
                dp[i] = max(dp[i], dp[i-len] + mx * len);
            }
        }
        return dp[n];
    }
};

import java.util.*;
class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int max = 0;
            for (int len = 1; len <= Math.min(k, i); len++) {
                max = Math.max(max, arr[i - len]);
                dp[i] = Math.max(dp[i], dp[i - len] + max * len);
            }
        }
        return dp[n];
    }
}

复杂度

面试官可能追问