LeetCode 1043. 分隔数组以得到最大和

约 4 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 美团
标签
数组 动态规划

题目描述

✅ 1043. 分隔数组以得到最大和

image-20260929073552751

题意分析

将非负整数数组按原顺序切成若干段，每段必须连续、非空且长度不超过 k。一段内所有元素都变成该段的最大值，求转换后整个数组元素和的最大值。

每个元素必须且只能属于一段，不能重排、遗漏或让分段重叠。不同段可以取不同长度，不要求每段都达到 k；只需返回最大总和，不必真正改写数组。

解法：动态规划状态转移

核心思路

[!blue]

定义 dp[i] 为前 i 个元素全部分段后的最大总和。任何一个前缀方案都有最后一段，设它的长度为 len，则前面剩下 i - len 个元素，其最优贡献是 dp[i - len]。

最后一段对应原数组的 [i - len, i)。这一段的每个位置都变成段内最大值 maxVal，所以整段贡献为 maxVal * len。固定末段后，前面的分段不会影响它，前缀当然应使用已经求出的最优方案，于是候选总和为 dp[i - len] + maxVal * len。

枚举 len = 1..min(k, i)，就覆盖了最后一段的全部合法长度；所有候选中取最大值，得到 dp[i]。这些前驱状态都比 i 小，因此按前缀长度从小到大计算即可。

枚举末段长度时，它每增加一格，只是在左边新增 arr[i - len]，可以顺手更新最大值，不必每次重新扫描整段。每换一个前缀 i，候选末段范围也变了，需要重新初始化 maxVal。

dp[0] = 0 表示空前缀没有贡献，让最后一段恰好覆盖当前全部前缀时也能使用同一个转移。数组非负，所以状态与本轮最大值从零开始合法。

解题步骤

  1. 创建长度为 n + 1 的 dp，初始全零。
  2. 对前缀长度 i = 1..n，重新令 maxVal = 0。
  3. 将末段长度从 1 增加到 min(k, i)，先把新加入的左端元素纳入段内最大值。
  4. 用 dp[i - len] + maxVal * len 更新当前前缀最优值。
  5. 所有前缀计算完成后返回 dp[n]。

代码实现

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        // dp[i] 表示前 i 个元素的最优结果，dp[0] 对应空前缀。
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            // 每个新前缀重新枚举最后一段，最大值不能沿用上一个前缀。
            int maxVal = 0;

            // 末段长度不能超过 k，也不能越过当前前缀的起点。
            for (int len = 1; len <= Math.min(k, i); len++) {
                // 最后一段向左扩展，先更新段内最大值，再计算候选贡献。
                maxVal = Math.max(maxVal, arr[i - len]);
                // 枚举最后一段，连接此前已求出的最优前缀。
                dp[i] = Math.max(dp[i], dp[i - len] + maxVal * len);
            }
        }

        return dp[n];
    }
}

func maxSumAfterPartitioning(arr []int, k int) int {
    n := len(arr)
    // dp[i] 表示前 i 个元素的最优结果，dp[0] 对应空前缀。
    dp := make([]int, n+1)

    for i := 1; i <= n; i++ {
        // 每个新前缀重新枚举最后一段，最大值不能沿用上一个前缀。
        maxVal := 0
        limit := k
        if i < limit {
            limit = i
        }
        // 末段长度不能超过 k，也不能越过当前前缀的起点。
        for length := 1; length <= limit; length++ {
            // 最后一段向左扩展，先更新段内最大值，再计算候选贡献。
            if arr[i-length] > maxVal {
                maxVal = arr[i-length]
            }
            // 枚举最后一段，连接此前已求出的最优前缀。
            candidate := dp[i-length] + maxVal*length
            if candidate > dp[i] {
                dp[i] = candidate
            }
        }
    }
    return dp[n]
}

复杂度分析

  • 时间复杂度：$O(nk)$，每个前缀最多枚举 k 个末段长度。
  • 空间复杂度：$O(n)$，保存前缀最优值。

关键点总结

[!green]

  • 按最后一段拆开完整方案，前缀与末段独立，才能直接使用最优子问题。
  • 状态下标是元素数量，末段左端下标恰好为 i - len。
  • 末段向左增量扩展，每个候选只需更新一次最大值，保持每个前缀最多 k 次工作。

易错点总结

[!yellow]

  • 固定每段都取 k 个元素，只枚举了一种切法，可能错过不同长度组合。
  • 先计算末段贡献再加入新左端，会用缺少一个元素的旧最大值参与转移。
  • 换一个前缀后仍沿用旧 maxVal，会混入不属于当前段的元素。
  • 末段长度超过 i 会访问负下标，超过 k 则违反题目要求，两侧限制都要保留。
  • 直接覆盖 dp[i]，会丢掉此前更优的末段选择，应在所有候选之间取最大。

相似题目

题目 难度 关联与区别
813. 最大平均值和的分组 中等 同样对前缀枚举最后一段，本题段长最多k且收益为段最大值乘长度，原题固定分组数并累加平均值。
1105. 填充书架 中等 同样保持输入顺序分段，并逐步维护一段内的最大值，原题还限制段内总宽度。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/92396509
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！