分割数组的最大值

数组有 n−1 个可分割位置，从中选择 k−1 个位置共有 C(n−1,k−1) 种方案。直接枚举不适合较大的输入。

把候选答案记为 cap，判断能否让每段和都不超过 cap。若 cap 可行，更大的上限也可行，因此可以二分查找最小可行上限。

令 cap 不小于最大元素。从左向右累加，加入下一个元素会超过上限，就开始新段。对于非负数组，这种贪心方式得到最少段数。

搜索下界：最大元素：每个元素都必须属于某一段。由于元素非负，该段和至少等于这个元素，因此答案下界是最大元素 10。

二分范围 · 上界 = 全部之和：全部元素的和为 32。非负数组进一步分段不会使某段和超过总和，因此 32 是可行上界。初始搜索区间为 [10,32]。

第1轮 · 取 mid：第一轮计算 mid=⌊(10+32)/2⌋=21。检查是否能分成不超过 2 段，且每段和都不超过 21。

cap=21 · 加入 nums[0]=7：读到 7，当前段和变为 7，段数为 1。绿色区域表示当前段包含的元素。

cap=21 · 加入 nums[1]=2：加入 2 后，当前段和为 9，没有超过上限 21，因此保持在同一段。

cap=21 · 加入 nums[2]=5：继续加入 5，当前段和为 14。第一段目前包含 [7,2,5]。

cap=21 · nums[3]=10 加入后超限 → 分段：若再加入 10，段和将变为 24，超过上限 21。在 10 之前分段，新段和为 10，总段数变为 2。

cap=21 · 加入 nums[4]=8：加入最后的 8 后，第二段和为 18，没有超过 21。遍历结束，得到 [7,2,5] 和 [10,8] 两段。

cap=21 · 可行 → 收紧上界：最少需要 2 段，不超过 k=2，因此 cap=21 可行。保留 21 作为候选，更新 hi=21。

第2轮 · 取 mid：第二轮在 [10,21] 中取下取整中点，mid=⌊31/2⌋=15。重新从数组开头检查 cap=15。

cap=15 · 段1 累加至 [7,2,5]：前 3 个元素之和为 14，不超过 15，仍可组成第一段 [7,2,5]。

cap=15 · nums[3]=10 加入后超限 → 分段：加入 10 会得到 24，大于 15，因此在 10 之前分段。第二段当前只有 10。

cap=15 · nums[4]=8 加入后超限 → 再分段：第二段再加入 8 会得到 18，仍大于 15，因此 8 必须开始第三段。最终需要 3 段。

cap=15 · 不可行 → 抬高下界：3 段超过 k=2，因此 cap=15 不可行。更小的上限也不可能可行，更新 lo=16，搜索区间变为 [16,21]。

第3轮 · 取 mid：第三轮计算 mid=⌊(16+21)/2⌋=18，检查 cap=18 的分段结果。

cap=18 · 段1 累加至 [7,2,5]：前 3 个元素仍组成和为 14 的第一段。加入下一项 10 会超过上限 18。

cap=18 · nums[3]=10 加入后超限 → 分段：在 10 之前分段，第二段的当前和为 10，总段数变为 2。

cap=18 · 加入 nums[4]=8：第二段加入 8 后，段和恰好为 18。段和等于上限，仍可继续使用当前段，最终只需要 2 段。

cap=18 · 可行 → 收紧上界：cap=18 可行，更新 hi=18。最小可行值仍可能更小，继续在 [16,18] 中搜索。

第4轮 · 取 mid：第四轮取 mid=17。需要判断 17 是否仍能满足最多 2 段的要求。

cap=17 · 贪心切出 3 段：cap=17 时，14+10 和 10+8 都超过上限，需要 [7,2,5]、[10]、[8] 三段。因此不可行，更新 lo=18。

二分收敛 · lo == hi：此时 lo=hi=18，搜索结束。18 可行，17 不可行，因此 18 就是最小可行上限。

最优分段结果：按 cap=18 分割，得到 [7,2,5] 和 [10,8]，最大段和为 18。这与二分查找得到的答案一致。

边界情况：当 k=1 时返回总和；k=n 时返回最大元素；全部元素为 0 时返回 0。上下界相等时不进入二分循环。

二分答案要求可行性具有单调性，也要求判定函数正确。本题的贪心判定依赖元素非负，不能直接用于含负数的数组。

面试追问：含负数时，存在可行分段这一条件对 cap 仍然单调；失效的是当前贪心判定和 max(nums) 下界。例如 [5,-4] 分成一段时答案为 1。