分割数组的最大值

怎样从“nums 分 m 段最小最大段和=15。”推导出 二分答案 · 分割和，并证明每次状态变化都不会漏掉答案？

中心结论：二分答案 mid:贪心看能否≤m 段每段≤mid;缩边界。

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意: 数组长度 n 满足以下条件:

1 ≤ n ≤ 1000 1 ≤ m ≤ min(50, n)

在本站主例中，nums 分 m 段最小最大段和=15。

算法最终需要得到或观察：最小最大段和 15。

枚举每一个可能答案会做大量相似验证；可行性单调时，可以直接在答案空间二分。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“答案可行性刻度”，明确答案需要观察什么。
2. 2状态只维护 lo/hi 答案、贪心段数。
3. 3转移每一步按照 二分答案 mid:贪心看能否≤m 段每段≤mid;缩边界。
4. 4收尾读取 最小最大段和 15。，并复核边界与复杂度。

先证明答案越大或越小时，可行性只朝一个方向变化。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：lo/hi 答案、贪心段数。

给出一个数组和分割的个数 M。要求把数组分成 M 个子数组，输出子数组和的最大值。 这一题可以用动态规划 DP 解答，也可以用二分搜索来解答。这一题是二分搜索里面的 max-min 最大最小值问题。题目可以转化为在 `M` 次划分中，求一个 `x`，使得 `x` 满足：对任意的`S(i)`，都满足 `S(i) ≤ x`。这个条件保证了 `x` 是所有 `S(i)` 中的最大值。要求的是满足该条件的最小的 `x`。`x` 的搜索范围在 `[max, sum]` 中。逐步二分逼近 low 值，直到找到能满足条件的 low 的最小值，即为最终答案。

二分答案 mid:贪心看能否≤m 段每段≤mid;缩边界。

执行过程中持续维护：lo/hi 答案、贪心段数。

正确性依赖以下不变量：验证函数单调,可二分答案。

面试时可以压缩为：二分+贪心验证 O(n log S)。

落到当前题，执行机制可以压缩为：二分答案 mid:贪心看能否≤m 段每段≤mid;缩边界。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入nums 分 m 段最小最大段和=15。 因为：二分答案 mid:贪心看能否≤m 段每段≤mid;缩边界。
2. 2二分答案:最小最大子数组和答案在范围内单调。 因为：limit 越大越容易 split。
3. 3mid=21 可行,尝试更小收缩上界。 因为：二分最小可行值。
4. 4mid=15 不可行,需要更大提高下界。 因为：二分最小可行值。
5. 5mid=18 可行,尝试更小收缩上界。 因为：二分最小可行值。
6. 6mid=17 不可行,需要更大提高下界。 因为：二分最小可行值。
7. 7最小可能的最大段和 = 18lo==hi 即答案。 因为：O(n log sum) 答案二分。
8. 8收尾与复杂度最小最大段和 15。 因为：时间 O(n) · 空间 O(1)。二分答案 mid:贪心看能否≤m 段每段≤mid;缩边界。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func splitArray(nums []int, m int) int {
	maxNum, sum := 0, 0
	for _, num := range nums {
		sum += num
		if num > maxNum {
			maxNum = num
		}
	}
	if m == 1 {
		return sum
	}
	low, high := maxNum, sum
	for low < high {
		mid := low + (high-low)>>1
		if calSum(mid, m, nums) {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

func calSum(mid, m int, nums []int) bool {
	sum, count := 0, 0
	for _, v := range nums {
		sum += v
		if sum > mid {
			sum = v
			count++
			// 分成 m 块，只需要插桩 m -1 个
			if count > m-1 {
				return false
			}
		}
	}
	return true
}

func main() {
    // 1. 主例
    //    输入：mode="split-array", nums=[7,2,5,10,8], m=2
    //    期望：最小最大段和 15。
    //
    // 2. 失败 / 未命中
    //    检查：贪心验证要线性扫累加切段。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC875 香蕉；LC1011 船运
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意nums 分 m 段最小最大段和=15。
2. 2重复枚举每一个可能答案会做大量相似验证；可行性单调时，可以直接在答案空间二分。
3. 3优化二分答案 mid:贪心看能否≤m 段每段≤mid;缩边界。
4. 4证明验证函数单调,可二分答案。
5. 5复杂度时间 O(n)，空间 O(1)