分割数组的最大值

直接枚举每一种切法、算每种的最大段和再取最小——切法数量是组合级的，n=1000、k=50 时根本算不完。得换个思路。

关键翻转：不枚举怎么切，而是猜一个上限 cap。「最大段和 ≤ cap 是否可行」对 cap 是单调的——cap 越大越容易满足。于是答案落在一条单调线上，可以二分。

怎么判一个 cap 行不行？能塞就塞、塞不下就切，贪心地用最少的段数装完。最后段数 ≤ k → cap 可行(段数少了把某段再切开总行)；段数 > k → cap 太小、装不下。下面盯住 cap、当前段和、段数怎么动。

二分范围 · 下界 = 最大单值：cap 的下界：再怎么切，最大的那个数 10 总得单独待在某段里，所以 cap 不可能小于 10。lo 从 10 起。

二分范围 · 上界 = 全部之和：cap 的上界：极端情况只切 1 段(k=1)，那段和就是全部之和 32。所以答案一定落在 [10, 32] 这个区间里，接下来在它上面二分。

第1轮 · 取 mid：第一轮取中点 mid = 21，意思是「假设最大段和不超过 21，够不够 2 段装完?」。下面贪心地从左往右塞一遍。

cap=21 · 塞 nums[0]=7：从第一个数 7 开始：当前段和 cur = 7，没超过 cap=21，装进段1。绿色表示已经在当前段里。

cap=21 · 塞 nums[1]=2：再塞 2，cur = 9，仍 ≤ 21，继续留在段1。

cap=21 · 塞 nums[2]=5：塞 5，cur = 14，还没满。段1 现在是 [7,2,5]，和 14。

cap=21 · nums[3]=10 塞不下 → 切：到 10 时 14+10 = 24 超过 cap=21，当前段塞不下了 → 在这里切一刀，把 10 放进新的段2，段数变成 2。前面的段1 已封口(变灰)。

cap=21 · 塞 nums[4]=8：最后塞 8，段2 的 cur = 18 ≤ 21，装得下。扫完全部，一共切出 2 段：[7,2,5] 和 [10,8]。

cap=21 · 可行 → 收紧上界：段数 2 正好 ≤ k=2，cap=21 可行!但我们要的是「最小的可行 cap」，所以把上界收到 hi=21，继续往小里试。区间变成 [10, 21]。

第2轮 · 取 mid：新区间 [10, 21] 取中点 mid = 15，试更紧的 cap=15。再贪心扫一遍。

cap=15 · 段1 装到 [7,2,5]：7、2、5 一路塞进段1，cur = 14，刚好 ≤ 15。和上一轮一样，段1 还是 [7,2,5]。

cap=15 · nums[3]=10 塞不下 → 切：10 又塞不下(24 > 15)，切一刀，段2 = [10]，段数到 2。

cap=15 · nums[4]=8 又塞不下 → 再切：这回到 8 时，段2 的 10+8 = 18 也超了，又得切一刀，8 单独成段3。cap 太小，逼出了 3 段。

cap=15 · 不可行 → 抬高下界：段数 3 > k=2，cap=15 太小、不可行。说明答案至少比 15 大，把下界抬到 lo = 16。区间变成 [16, 21]。

第3轮 · 取 mid：区间 [16, 21] 取中点 mid = 18，试 cap=18。

cap=18 · 段1 装到 [7,2,5]：7、2、5 进段1，cur = 14 ≤ 18。

cap=18 · nums[3]=10 塞不下 → 切：10 塞不下(24 > 18)，切，段2 = [10]，段数 2。

cap=18 · 塞 nums[4]=8：8 进段2，cur = 18，恰好等于 cap=18(等于也算装得下)。扫完 2 段，cap=18 可行。

cap=18 · 可行 → 收紧上界：段数 2 ≤ k，cap=18 可行，hi 收到 18。区间只剩 [16, 18]，还能再挤吗?再来一轮。

第4轮 · 取 mid：区间 [16, 18] 取中点 mid = 17，试比 18 更小的 cap=17，看能不能再省。

cap=17 · 贪心切出 3 段：cap=17 时和 cap=15 一样：[7,2,5] 后切，[10] 后 10+8=18 又超 17 再切，逼出 3 段。不可行，lo 抬到 mid+1 = 18。

二分收敛 · lo == hi：lo 和 hi 都到了 18，二分停下。18 就是最小的可行 cap——也就是最优切法下那个「最大段和」。

答案 · 按 cap=18 落刀：用 cap=18 落刀，切成 [7,2,5] 和 [10,8]，两段和 14 与 18，最大就是 18。和题目答案一致，搞定。

边界三连：两个极端 k=1(整段)和 k=n(单点成段)正好对应区间的上下界 sum 和 max——区间设计天然兜住。

「二分答案」是一类大套路：当「最优值」不好直接求、但「某个值行不行」好判且单调时，就二分这个值本身。LC1011 在 D 天内送达、LC875 吃香蕉速度都是同一招。

面试追问：把「可行性的单调性」和「与 DP 的取舍」讲透，是这题的面试加分项。