410. 分割数组的最大值
题目描述
输入一个非负整数数组 nums 和一个整数 k。把 nums 切成恰好 k 段，每段都是非空的连续子数组，所有段合起来正好是原数组。
对每种切法，计算各段元素和中的最大值。返回所有切法里这个最大值能取到的最小值。
示例 1
输入：nums = [7,2,5,10,8], k = 2 输出：18
解释：切成 [7,2,5] 和 [10,8]，两段和为 14 和 18，最大值 18 是所有切法中最小的。
示例 2
输入：nums = [1,2,3,4,5], k = 2 输出：9
解释：切成 [1,2,3] 和 [4,5]，两段和为 6 和 9。
数据范围
1 <= nums.length <= 10000 <= nums[i] <= 10^61 <= k <= min(50, nums.length)
解题思路：二分答案 + 贪心
反过来问：“每段和不超过 mid 时，最少要分几段？”贪心地从左往右装，装不下就开新段，得到最少段数 cnt。mid 越大 cnt 越小，具有单调性，所以在 [max(nums), sum(nums)] 上二分：cnt <= k 说明 mid 可行（段数少了可以再拆开），往小找；否则往大找。
为什么正确
答案始终在 [lo, hi] 内：hi 总是可行的上限，lo 左边的值都已确认不可行。
复杂度分析
时间 O(n log S)，S 为数组和。额外空间 O(1)。
易错点
下界要取 max(nums) 而不是 0，否则单个大元素装不进任何段，贪心计数会出错。判断条件是 cnt <= k，不是 cnt == k。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo + hi) // 2
cnt, cur = 1, 0
for x in nums:
if cur + x > mid:
cnt += 1
cur = 0
cur += x
if cnt <= k:
hi = mid
else:
lo = mid + 1
return loclass Solution {
public int splitArray(int[] nums, int k) {
int lo = 0, hi = 0;
for (int x : nums) {
lo = Math.max(lo, x);
hi += x;
}
while (lo < hi) {
int mid = (lo + hi) / 2;
int cnt = 1, cur = 0;
for (int x : nums) {
if (cur + x > mid) {
cnt += 1;
cur = 0;
}
cur += x;
}
if (cnt <= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
}class Solution {
public:
int splitArray(vector<int>& nums, int k) {
int lo = *max_element(nums.begin(), nums.end());
int hi = accumulate(nums.begin(), nums.end(), 0);
while (lo < hi) {
int mid = (lo + hi) / 2;
int cnt = 1, cur = 0;
for (int x : nums) {
if (cur + x > mid) {
cnt += 1;
cur = 0;
}
cur += x;
}
if (cnt <= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
};func splitArray(nums []int, k int) int {
lo, hi := 0, 0
for _, x := range nums {
lo = max(lo, x)
hi += x
}
for lo < hi {
mid := (lo + hi) / 2
cnt, cur := 1, 0
for _, x := range nums {
if cur+x > mid {
cnt += 1
cur = 0
}
cur += x
}
if cnt <= k {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}var splitArray = function(nums, k) {
let lo = Math.max(...nums), hi = nums.reduce((a, b) => a + b, 0);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
let cnt = 1, cur = 0;
for (const x of nums) {
if (cur + x > mid) {
cnt += 1;
cur = 0;
}
cur += x;
}
if (cnt <= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};function splitArray(nums: number[], k: number): number {
let lo = Math.max(...nums), hi = nums.reduce((a, b) => a + b, 0);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
let cnt = 1, cur = 0;
for (const x of nums) {
if (cur + x > mid) {
cnt += 1;
cur = 0;
}
cur += x;
}
if (cnt <= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}其他解法
动态规划枚举每种切分位置求最优值；二分答案利用“最大段和越大越容易满足”的单调性，配合贪心检查，复杂度低得多。
解法 2：动态规划 时间 O(n²k)，空间 O(nk)
设 S 为数组元素之和。f[i][j] 表示把前 i 个数分成 j 段时，各段和最大值的最小可能值。枚举最后一段的起点 p，f[i][j] = min(max(f[p][j - 1], sum(p..i-1)))，区间和用前缀和 O(1) 求出。初始 f[0][0] = 0，其余为无穷大，答案是 f[n][k]。
直接按定义划分状态，思路自然，不依赖答案的单调性。复杂度 O(n²k)，n = 1000、k = 50 时约 5×10⁷ 次运算，明显慢于二分答案。
class Solution:
def splitArray(self, nums, k):
n = len(nums)
pre = [0] * (n + 1)
for i, x in enumerate(nums):
pre[i + 1] = pre[i] + x
INF = float('inf')
f = [[INF] * (k + 1) for _ in range(n + 1)]
f[0][0] = 0
for i in range(1, n + 1):
for j in range(1, min(i, k) + 1):
best = INF
for p in range(j - 1, i):
cur = max(f[p][j - 1], pre[i] - pre[p])
if cur < best:
best = cur
f[i][j] = best
return f[n][k]class Solution {
public int splitArray(int[] nums, int k) {
int n = nums.length;
long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
long[][] f = new long[n + 1][k + 1];
for (long[] row : f) Arrays.fill(row, Long.MAX_VALUE);
f[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= Math.min(i, k); j++)
for (int p = j - 1; p < i; p++)
f[i][j] = Math.min(f[i][j], Math.max(f[p][j - 1], pre[i] - pre[p]));
return (int) f[n][k];
}
}class Solution {
public:
int splitArray(vector<int>& nums, int k) {
int n = nums.size();
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
const long long INF = LLONG_MAX;
vector<vector<long long>> f(n + 1, vector<long long>(k + 1, INF));
f[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= min(i, k); j++)
for (int p = j - 1; p < i; p++)
f[i][j] = min(f[i][j], max(f[p][j - 1], pre[i] - pre[p]));
return (int)f[n][k];
}
};func splitArray(nums []int, k int) int {
n := len(nums)
pre := make([]int, n+1)
for i, x := range nums {
pre[i+1] = pre[i] + x
}
const INF = math.MaxInt64
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, k+1)
for j := range f[i] {
f[i][j] = INF
}
}
f[0][0] = 0
for i := 1; i <= n; i++ {
for j := 1; j <= min(i, k); j++ {
for p := j - 1; p < i; p++ {
f[i][j] = min(f[i][j], max(f[p][j-1], pre[i]-pre[p]))
}
}
}
return f[n][k]
}var splitArray = function(nums, k) {
const n = nums.length;
const pre = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
const f = Array.from({ length: n + 1 }, () => new Array(k + 1).fill(Infinity));
f[0][0] = 0;
for (let i = 1; i <= n; i++)
for (let j = 1; j <= Math.min(i, k); j++)
for (let p = j - 1; p < i; p++)
f[i][j] = Math.min(f[i][j], Math.max(f[p][j - 1], pre[i] - pre[p]));
return f[n][k];
};function splitArray(nums: number[], k: number): number {
const n = nums.length;
const pre = new Array<number>(n + 1).fill(0);
for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
const f: number[][] = Array.from({ length: n + 1 }, () => new Array<number>(k + 1).fill(Infinity));
f[0][0] = 0;
for (let i = 1; i <= n; i++)
for (let j = 1; j <= Math.min(i, k); j++)
for (let p = j - 1; p < i; p++)
f[i][j] = Math.min(f[i][j], Math.max(f[p][j - 1], pre[i] - pre[p]));
return f[n][k];
}