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

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

题目描述

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

题意分析

把数组切成若干连续子数组，每段长度不超过 k，然后把每段里的所有元素都替换成该段的最大值，求替换之后整个数组的和最大是多少。

有三个信息决定了解法形态。第一，切分必须是连续分段——不能跳着选元素，也不能重排，这让「前缀」成为天然的子问题边界。第二，每段的贡献只与「段长」和「段内最大值」有关，与段内其他元素完全无关，所以一段的收益是 段最大值 × 段长。第三，段长上限是 k，这是一个很小的常数，意味着「最后一段有多长」只有 k 种可能，可以直接枚举。

于是问题的形状就清楚了：整个数组的最优切分 = 某个前缀的最优切分 + 最后一段的收益。前缀的最优解与「最后一段怎么切」互不干扰，因为分段是连续且不重叠的，前缀内部怎么切都不会改变最后一段的最大值。这条无后效性正是可以做动态规划的依据。

约束是 1 ≤ arr.length ≤ 500、1 ≤ k ≤ arr.length、0 ≤ arr[i] ≤ 10^9。数组长度只有 500，$O(nk)$ 最多 25 万次操作，非常宽松；但元素可以到 $10^9$，段长可以到 500，单段贡献可达 $5 \times 10^{11}$，必须警惕溢出——好在题目保证最终答案不超过 32 位整数范围，中间的 maxVal * len 只要不脱离合法切分也在范围内。

边界：k 可能等于 1（每段只能一个元素，答案就是原数组之和）；k 也可能等于数组长度（可以整段合并，答案是 max × n 与其他切法中的较大者）；元素允许为 0，不影响任何逻辑。

解法：动态规划状态转移

核心思路

这是连续分段问题，最后一段之前的部分仍是同类子问题。定义：

dp[i] 表示前 i 个元素 arr[0..i-1] 完成合法分段后的最大和，dp[0] = 0。

枚举最后一段长度 len，其中 1 <= len <= min(k, i)。最后一段是 arr[i-len..i-1]，若段内最大值为 maxVal，它对答案的贡献为 maxVal * len，因此：

dp[i] = max(dp[i-len] + max(arr[i-len..i-1]) * len)

内层让 len 从 1 递增，最后一段每次只向左扩展一个元素，于是可同步更新 maxVal = max(maxVal, arr[i-len])，不必为每个候选区间重新扫描。

不变量：处理某个 len 时，maxVal 恰好是 arr[i-len..i-1] 的最大值，而 dp[i-len] 已是这段之前前缀的最优值。

正确性：任意合法切分都有唯一的最后一段长度，枚举会覆盖它；固定最后一段后，若前缀不用 dp[i-len] 的最优方案，替换成最优方案只会让总和更大。因此转移覆盖所有方案并为每个最后一段选择最优前缀，取最大值即得到 dp[i]。

解题步骤

  1. 创建长度为 n + 1 的 dp，保留 dp[0] = 0 表示空前缀。
  2. 按 i = 1..n 计算每个前缀，保证转移依赖的较短前缀已经完成。
  3. 对当前 i 枚举 len = 1..min(k,i)，先把 arr[i-len] 纳入 maxVal，再更新 dp[i]。
  4. 返回 dp[n]。

样例 [1,15,7,9,2,5,10]、k = 3 中，最终状态 dp[7] = 84，对应切分 [1,15,7] | [9] | [2,5,10]，贡献为 15*3 + 9 + 10*3。

不能贪心地总取长度 k：[1,4,1,5,7,3,6,1,9,9,3]、k = 4 固定切成 4+4+3 得 75，而最优切分可得 83。最后一段长度必须完整枚举。

代码实现

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 maxVal = 0;
            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 := make([]int, n+1)

	for i := 1; i <= n; i++ {
		maxVal := 0
		limit := k
		if i < limit {
			limit = i
		}
		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)$。共有 n 个状态，每个状态枚举至多 k 个最后一段长度；段内最大值增量维护为 $O(1)$。
  • 空间复杂度：$O(n)$，来自 dp 数组。

关键点总结

  • 连续划分的常用状态是「前 i 个元素的最优值」，转移则枚举最后一段。
  • 用元素个数作为状态下标，dp[0] 能自然表示空前缀并消除边界特判。
  • dp 默认初始化为 0 在本题成立，是因为元素均非负、所有合法候选也非负；若扩展到允许负数，除 dp[0] 外必须初始化为负无穷，避免把“尚未转移”误当成答案 0。
  • 最后一段从右向左逐个扩展时，段内最大值可以增量维护，使转移保持 $O(nk)$。
  • dp[i] 的每个候选必须由「已求最优的前缀」与「当前最后一段贡献」两部分组成。

易错点总结

  • maxVal 没有在每个 i 开始时重置：旧前缀的最大值会泄漏到当前最后一段，样例可能得到大于 84 的非法结果。
  • 先转移、后更新最大值：[1,15]、k = 2 会漏算当前纳入的元素，正确答案应为 30。
  • 忘记限制 len <= i：[5]、k = 3 会访问 arr[-1]。
  • 忘记限制 len <= k：[1,15,7]、k = 1 会非法合并整段得到 45，正确答案是 23。
  • 转移时直接覆盖 dp[i] 而不取最大值：[10,1,1]、k = 2 可能被较差候选覆盖成 12，正确答案是 21。
  • 返回 dp[n-1]：状态下标表示元素个数，完整数组对应 dp[n]。
  • 若扩展题不再保证答案落在 32 位范围内，Java 应改用 long、Go 应改用 int64 保存乘积和状态。

相似题目

题目 难度 考察点
813. 最大平均值和的分组 中等 限制从「段长上限」变成「段数上限」，dp 要多加一维记录已用段数，段收益改成平均值
1105. 填充书架 中等 同为枚举最后一段，但段的合法性由累计宽度决定、收益是段内最大高度，求最小值
132. 分割回文串 II 困难 段的合法性是「必须是回文」，需要先预处理回文表才能让转移保持 $O(1)$
139. 单词拆分 中等 dp[i] 变成布尔可行性而非最优值，段的合法性靠字典查询
91. 解码方法 中等 段长上限固定为 2 的计数型划分 DP，转移求的是方案数
410. 分割数组的最大值 困难 目标是最小化各段和的最大值，除了 $O(n^2 k)$ 的 DP 还有二分答案的更优解法