Split Array Largest Sum
给你一个由非负整数组成的数组 nums 和一个整数 k。将 nums 恰好分成 k 部分，每部分都是一段非空的相邻元素，并且各部分保持原有顺序。每部分都有一个总和，划分的代价是这些总和中的最大值。
返回将数组分成 k 部分后可能达到的最小代价。
函数
- numsinteger-array
- 按顺序排列的非负值
- kinteger
- 要将它们切分成的连续部分数量
- 返回值integer
- 最大部分和的最小可能值
约束条件
1 ≤ nums.length ≤ 50000 ≤ nums[i] ≤ 1051 ≤ k ≤ nums.length- 每个部分都至少包含一个值。所有值均为 0 的部分，其总和为 0，这是允许的。
示例
- 输入
- nums = [6, 2, 9, 4, 7, 3]k = 3
- 输出
- 13
- 解释
- 拆分为
[6, 2]、[9, 4]、[7, 3]的成本是 13。没有任何拆分的成本是 12：从左到右打包各部分，且每组不超过 12，会得到[6, 2]、[9]、[4, 7]、[3]，共四组。
- 输入
- nums = [8, 1, 1, 1, 5]k = 2
- 输出
- 8
- 解释
- 8 位于某个部分中，因此任何拆分的代价都不会低于 8。
[8]和[1, 1, 1, 5]的总和都是 8。
- 输入
- nums = [3, 0, 4]k = 3
- 输出
- 4
- 解释
- 3 个值分成 3 份，每份有 1 个值，各份的和分别为 3、0 和 4。某一份的和为 0 也是允许的。
进阶
使用前缀和，贪心检查可以通过二分查找找出每一部分的结束位置。当 k 较小时，整个方法的速度有多快？
提示
逐个打开提示，每个都会多透露一点。
假设有人保证，最大的部分之和最多为
c。你能快速判断k个部分是否足够吗？从左到右填充各部分，只有当下一个值会使总和超过
c时，才结束当前部分。这样得到的部分数量最少，而且c越大，所需的部分不会更多。在最大值和总和之间对
c进行二分查找。如果贪心计数至多为k，那么答案是c或更小；否则答案更大。
题解
即使使用动态规划，直接搜索最佳分割方式的代价也需要 O(k·n²)。换个角度思考：给定一个上限，能否用 k 个部分满足要求？一次贪心遍历就能回答这个问题。随着上限增大，答案会从否变为是，而且只会变化一次。二分查找就能找到这个转折点。
前缀上的动态规划
结果正确，但无法在最大的测试中运行完毕
思路
用 best[p][j] 表示将前 j 个值切分成 p 个部分时的最小代价。如果最后一部分是 nums[i..j-1]，代价就是 best[p-1][i] 和该部分总和中的较大值，而前 i 个值的最佳切分方式不受其后任何内容影响。因此，best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i])，其中 i 从 p-1 到 j-1，以确保每个部分都至少包含一个值。第 p 行只读取第 p-1 行，因此两行就足够了。
最多需要运行 k·n²/2 步：当 n = 5000 且 k = 2500 时，大约需要 1.8 × 10^10 步。
算法
- 构建
prefix，其中prefix[j]是前j个值的和，并将best[j] = prefix[j]设为分成一部分时的结果。 - 对于从 2 到
k的每个部分数p，以及从p到n的每个结束位置j，在从p-1到j-1的i中，取max(best[i], prefix[j] - prefix[i])的最小值。 - 将这些最小值存入新的一行，并将其设为
best。 - 返回
best[n]。
def splitArray(nums, k):
n = len(nums)
# prefix[j] is the sum of the first j values
prefix = [0] * (n + 1)
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x
# best[j]: the smallest largest part when the first j values form one part
best = prefix[:]
for parts in range(2, k + 1):
nxt = [0] * (n + 1)
for j in range(parts, n + 1):
lowest = prefix[j] # never worse than one part holding everything
for i in range(parts - 1, j):
# the first i values form parts-1 parts, nums[i..j-1] is the last part
worst = max(best[i], prefix[j] - prefix[i])
if worst < lowest:
lowest = worst
nxt[j] = lowest
best = nxt
return best[n]在最大和中进行二分查找
思路
要测试上限 c，从左向右遍历，并在当前部分的总和不超过 c 时将值加入其中，然后开始新的一部分。这样得到的部分数最少。与任何有效划分相比，贪心算法的第一部分至少会延伸到同样靠右的位置，因此它的下一部分开始位置不会早于另一种划分。贪心算法在该部分结束位置之前包含的值，是某个符合条件的部分的一部分；由于没有负数，一部分的总和不会超过整个部分的总和。因此，贪心算法不会落后。
部分数少于 k 也和正好有 k 个部分一样好：将包含两个或更多值的部分切成两部分，总和不会增加。因此，测试条件是 partsNeeded(c) ≤ k。
在 max(nums) 和 sum(nums) 之间二分查找最小的可行上限。max(nums) 一定属于某个部分，而 sum(nums) 总能放进一个部分。
算法
- 将
lo = max(nums)和hi = sum(nums)设为初始值。 - 当
lo < hi时，取mid = lo + (hi - lo) / 2。 - 统计在
mid限制下贪心划分的部分数：先从 1 个部分开始，和为 0；如果加入一个值会超过mid，就增加一个部分，并将和重置为该值。 - 如果部分数至多为
k，就设置hi = mid；否则设置lo = mid + 1。 - 返回
lo。
def splitArray(nums, k):
def parts_needed(cap):
# Fill each part left to right and start a new one only when the next value would pass cap.
parts, current = 1, 0
for x in nums:
if current + x > cap:
parts += 1
current = x
else:
current += x
return parts
lo, hi = max(nums), sum(nums) # one value per part at best, everything in one part at worst
while lo < hi:
mid = (lo + hi) // 2
if parts_needed(mid) <= k:
hi = mid # mid works, so the answer is mid or smaller
else:
lo = mid + 1 # mid needs more than k parts, so the answer is larger
return lo
易错点和边界情况
- 从小于
max(nums)的lo开始。贪心算法会把大于上限的值单独放在一部分中，因此对于[1, 9]和k = 2，它会报告上限 5 可行。 - 测试
partsNeeded(c) == k。对于[3, 0, 4]和k = 3，上限为 4 时会打包成[3, 0]、[4]，所以没有任何上限能通过测试。 - 从 0 开始统计部分数，这会使统计结果少 1。
- 当
mid可行时设置hi = mid - 1，这样当答案就是mid时会错过答案。 - 让 DP 的
i从 0 开始。值的数量少于部分数的单元格会被当作代价 0 来读取，因此对于[100, 1, 1]和k = 3，结果会是 2，而不是 100。
常见问题3
拆分数组最大和的时间复杂度是多少？
时间复杂度为 O(n log S)，额外空间复杂度为 O(1)，其中 S 是 nums 的总和：每次贪心检查都只遍历一遍，且每次检查后上限范围都会减半。S = 5 × 10^8 时，大约需要 29 次检查。DP 需要 O(k·n²) 时间。
为什么可行性检查具有单调性？
如果拆分后的每一部分总和都不超过 c，那么同样的拆分也能满足 c+1。因此，只要某个上限可行，所有更大的上限也都可行，答案会先是一段否，然后是一段是。二分查找可以找到第一个是。
二分查找适用于负数吗？
不对。负值会拉低总和，因此贪心算法可能过早结束一部分；而拆分一部分后，其中一段的总和可能超过整个部分。动态规划不会做这两种假设，因此始终能得出正确结果。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def splitArray(nums, k):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [6, 2, 9, 4, 7, 3] k = 3
预期输出
13