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

分隔数组以得到最大和，到底在最大化什么

给整数数组 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。

Python

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]

C++

#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];
    }
};

Java

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];
    }
}