分割数组的最大值
给定一个非负整数数组 $nums$ 和一个整数 $k$，将数组分成 $k$ 个非空连续子数组，使得这 $k$ 个子数组各自和的最大值最小。返回分割后最小的和的最大值。
形式化定义
将数组 $nums[0..n{-}1]$ 切分为 $k$ 段连续子数组 $[0..p_1], [p_1{+}1..p_2], \ldots, [p_{k-2}{+}1..n{-}1]$。设第 $j$ 段的段和为 $S_j$，目标是：
样例 1
输入：nums = [7,2,5,10,8], k = 2
输出：18
解释：最优划分 $[7,2,5] \mid [10,8]$，段和分别为 $14$ 和 $18$，最大值为 $18$。其他方案的最大值都更大：
- $[7] \mid [2,5,10,8]$ → $\max(7, 25) = 25$
- $[7,2] \mid [5,10,8]$ → $\max(9, 23) = 23$
- $[7,2,5,10] \mid [8]$ → $\max(24, 8) = 24$
样例 2
输入：nums = [1,2,3,4,5], k = 2
输出：9
解释：最优划分 $[1,2,3,4] \mid [5]$，最大段和为 $9$。
直接枚举所有划分方案的组合数是指数级的。但注意到一个关键性质：
关键观察：单调性
观察 1：如果"最大段和不超过 $T$"有合法划分方案，那么对于任意 $T' > T$，也一定有合法方案（只需沿用同一个划分）。
观察 2：答案关于 $T$ 具有单调性——存在一个临界值 $T^*$，$T \ge T^*$ 时都有解，$T < T^*$ 时都无解。这正是二分答案的适用条件。
观察 3：给定 $T$，用贪心就能判断可行性——从左到右尽量往当前段塞元素，塞不下就断开新段。最终段数 $\le k$ 则 $T$ 可行。
二分答案的搜索范围：
- 下界 $L = \max(nums)$：最大段和至少要能装下最大的单个元素。
- 上界 $R = \sum(nums)$：所有元素放一段。
通用模式
「最小化最大值」或「最大化最小值」类问题，如果可行性关于答案具有单调性，几乎都可以用二分答案。这类题目在笔试中出现频率极高，流水线并行题 P4982 就是同一模式的加强版（多了显存约束）。
给定阈值 $T$，判断"最大段和 $\le T$ 时，能否划分为 $\le k$ 段"：
维护当前段和 $t$（初始 $0$）和段间断裂次数 $cnt$（初始 $0$）。遍历每个元素 $num$：
处理完所有元素后，$cnt$ 是断裂次数 = 段数 $- 1$。判断条件：
为什么贪心是对的？在固定 $T$ 的前提下，每段"尽量多塞"不会比"提前断开"更差——提前断开只会增加段数。贪心地让每段尽可能长，得到的段数最少，是最有希望满足 $\le k$ 的策略。
算法步骤：
- 二分范围 $L = \max(nums) - 1$，$R = \sum(nums) + 1$。
- 对每个 $mid$，贪心扫描统计断裂次数 $cnt$。
- 若 $cnt < k$（可行），收缩右界；否则收缩左界。
- 返回 $R$。
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
def check(T):
cnt = 0 # 断裂次数 = 段数 - 1
t = 0 # 当前段和
for num in nums:
if t + num <= T:
t += num
else:
cnt += 1
t = num
return cnt < k # 断裂次数 < k 等价于段数 ≤ k
L = max(nums) - 1 # L 停在"不可行"侧
R = sum(nums) + 1 # R 停在"可行"侧
while L + 1 != R:
mid = (L + R) // 2
if check(mid):
R = mid # 可行，尝试更小
else:
L = mid # 不可行，需要更大
return R
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间 | $O(n \log(\sum nums))$ | 二分 $\log(\sum nums)$ 轮，每轮 $O(n)$ 贪心扫描 |
| 空间 | $O(1)$ | 只用到常数额外变量 |
对于 $n \le 1000$，$\sum nums \le 10^9$ 的数据规模，$\log_2(10^9) \approx 30$，总操作量约 $3 \times 10^4$，效率极高。