企业官网建设流程全解析

Split Array Largest Sum（拆分数组的最大和）：从递归到二分答案的六种解法全解析

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读

Split Array Largest Sum（LeetCode 410，拆分数组的最大和）是一道经典的"最小化最大值"问题：给定一个非负整数数组nums与一个整数k，需要将数组拆分成k个连续非空子数组，使得这k个子数组各自和的最大值尽可能小，并返回这个最小可能值。本文基于 articles/split-array-largest-sum.md 的完整题解脉络，从暴力递归逐步演进到记忆化搜索、自底向上 DP、空间优化 DP，再到面试中最常被考察的"二分搜索答案 + 贪心校验"以及"二分 + 前缀和"优化，并对照当前仓库中 python/0410-split-array-largest-sum.py、java/0410-split-array-largest-sum.java、javascript/0410-split-array-largest-sum.js、kotlin/0410-split-array-largest-sum.kt 的真实实现逐一印证。读完本文，你将掌握"答案单调性"这一关键洞察，并能在任意支持的语言中独立写出最优解。

问题定义与前置知识

问题：给定整数数组nums（非负）与整数k，将nums拆分为k个连续子数组，最小化这些子数组和的最大值。

前置知识（原文 Prerequisites 部分）——掌握以下工具是解出本题的前提：

• 递归（Recursion）：枚举所有可能的切分点，递归求解子问题；
• 动态规划（Dynamic Programming）：使用记忆化（memoization）或表格化（tabulation）缓存重叠子问题；
• 二分搜索答案（Binary Search on Answer）：当校验函数具有单调性时，直接对答案候选值进行二分；
• 贪心算法（Greedy）：在给定候选答案（最大子数组和上限）时，贪心地"能放就放"来划分数组以验证可行性；
• 前缀和（Prefix Sums）：O(1) 计算任意子数组[i, j]的和，用于加速可行性校验。

这五块知识对应五种解法的演进路径：递归是 DP 的雏形，DP 优化掉重复计算，二分答案则彻底换一种思考方式，前缀和再把二分校验进一步加速。

方案 1：递归暴力枚举（Recursion）

思路（Intuition）

把问题拆成"当前第一个子数组切到哪里"，剩余部分递归地交给k - 1个子数组去处理。对于每一个可能的切分点，取"当前子数组和"与"递归返回的剩余部分最小最大和"两者的最大值（因为最终答案是所有子数组和的最大值），再在所有切分点中取最小值。

算法步骤

1. 定义dfs(i, m)：i为当前子数组起始下标，m为剩余要形成的子数组个数；
2. 边界条件：
   • 若i == n且m == 0，说明恰好用完所有元素与子数组，返回0（合法切分）；
   • 若i == n或m == 0二者之一不满足，返回无穷大（非法状态）；
3. 对当前子数组的每个可能终点j（从i到n - m，必须为后面的m - 1个子数组至少各留一个元素）：
   • 累加curSum（nums[i..j]的和）；
   • 递归求解dfs(j + 1, m - 1)；
   • 用min(res, max(curSum, dfs(j + 1, m - 1)))更新结果；
4. 返回dfs(0, k)。

代码实现（Python）

class Solution: def splitArray(self, nums: List[int], k: int) -> int: n = len(nums) def dfs(i, m): if i == n: return 0 if m == 0 else float("inf") if m == 0: return float("inf") res = float("inf") curSum = 0 for j in range(i, n - m + 1): curSum += nums[j] res = min(res, max(curSum, dfs(j + 1, m - 1))) return res return dfs(0, k)

复杂度

• 时间复杂度：$O(n \cdot 2^n)$ —— 每次递归都在枚举切分点，本质上遍历了所有切分方案；
• 空间复杂度：$O(n)$ —— 递归栈深度最多为k，但极端情况下接近n。

当n稍大（例如 30 以上）时该方案完全不可行，它存在的意义是作为后续优化方案的推导起点。

方案 2：动态规划 · 自顶向下（Top-Down DP / 记忆化搜索）

思路

观察递归版本：同样的(i, m)状态会被反复计算（例如不同切分路径都可能到达"从第 5 个元素开始、还剩 3 个子数组"）。把每个状态的结果缓存进一个二维记忆化表，重复状态直接返回缓存值即可。

算法步骤

1. 建立二维记忆化表dp[n][k+1]，初始化为-1（表示未计算）；
2. 递归结构与暴力法完全一致；
3. 计算前先查表：若dp[i][m] != -1直接返回；
4. 计算完状态(i, m)后写入dp[i][m]；
5. 返回dfs(0, k)。

代码实现（Python）

class Solution: def splitArray(self, nums: List[int], k: int) -> int: n = len(nums) dp = [[-1] * (k + 1) for _ in range(n)] def dfs(i, m): if i == n: return 0 if m == 0 else float("inf") if m == 0: return float("inf") if dp[i][m] != -1: return dp[i][m] res = float("inf") curSum = 0 for j in range(i, n - m + 1): curSum += nums[j] res = min(res, max(curSum, dfs(j + 1, m - 1))) dp[i][m] = res return res return dfs(0, k)

复杂度

• 时间复杂度：$O(k \cdot n^2)$ —— 状态数约n × k，每个状态的转移枚举O(n)个切分点；
• 空间复杂度：$O(k \cdot n)$ —— 记忆化表。

其中n为数组nums的长度，k为要拆分的子数组个数。

方案 3：动态规划 · 自底向上（Bottom-Up DP）

思路

把记忆化搜索反过来：从"小问题"（子数组个数少、起点靠后）开始填表，逐步构造出"大问题"的解。dp[i][m]表示把nums[i..n-1]拆成m个子数组时，能得到的最小最大子数组和。

算法步骤

1. 创建dp[n+1][k+1]并初始化为无穷大，基准条件dp[n][0] = 0（空后缀、0 个子数组，合法）；
2. 外层循环m从1到k（子数组个数由少到多）：
   • 内层循环起始下标i从n-1递减到0：
     • 枚举第一个子数组的终点j，累加curSum；
     • 更新dp[i][m] = min(dp[i][m], max(curSum, dp[j+1][m-1]))；
3. 返回dp[0][k]。

代码实现（Python）

class Solution: def splitArray(self, nums: List[int], k: int) -> int: n = len(nums) dp = [[float("inf")] * (k + 1) for _ in range(n + 1)] dp[n][0] = 0 for m in range(1, k + 1): for i in range(n - 1, -1, -1): curSum = 0 for j in range(i, n - m + 1): curSum += nums[j] dp[i][m] = min(dp[i][m], max(curSum, dp[j + 1][m - 1])) return dp[0][k]

复杂度

• 时间复杂度：$O(k \cdot n^2)$；
• 空间复杂度：$O(k \cdot n)$。

其中n为数组长度，k为子数组个数。

方案 4：动态规划 · 空间优化（Space Optimized DP）

思路

观察自底向上的递推式：计算dp[i][m]时只依赖dp[...][m-1]这一层的数据。因此无需保留完整的二维表，只需两个一维数组（当前层与上一层），每轮迭代后交换即可。

算法步骤

1. 创建两个一维数组dp与nextDp（长度均为n+1），初始化为无穷大，令dp[n] = 0；
2. 外层循环m从1到k：
   • 将nextDp重置为无穷大；
   • 对每个起始下标i，基于上一层的dp数组计算本轮结果写入nextDp；
   • 交换dp与nextDp；
3. 返回dp[0]。

代码实现（Python）

class Solution: def splitArray(self, nums: List[int], k: int) -> int: n = len(nums) dp = [float("inf")] * (n + 1) dp[n] = 0 for m in range(1, k + 1): nextDp = [float("inf")] * (n + 1) for i in range(n - 1, -1, -1): curSum = 0 for j in range(i, n - m + 1): curSum += nums[j] nextDp[i] = min(nextDp[i], max(curSum, dp[j + 1])) dp = nextDp return dp[0]

复杂度

• 时间复杂度：$O(k \cdot n^2)$（不变）；
• 空间复杂度：$O(n)$ —— 从二维表降为一维滚动数组。

其中n为数组长度，k为子数组个数。

方案 5：二分搜索答案（Binary Search on Answer）——推荐面试解法

思路

前四种方案都在"搜索切分方式"，而二分答案法换个角度：直接猜答案。

关键洞察是答案的上下界非常清晰：

• 下界l = max(nums)：单个元素自成子数组时，最大子数组和不可能小于最大元素（k = n的极限情形）；
• 上界r = sum(nums)：整个数组作为一个子数组时，和即为总和（k = 1的情形）。

而"能否用不超过x的最大子数组和完成k段拆分"是一个关于x的单调函数：x越大越容易满足。因此可以对答案二分，用贪心校验函数判断候选值是否可行：可行就记录并尝试更小值，不可行就调大。

算法步骤

1. 令l = max(nums)，r = sum(nums)；
2. 在l <= r上二分：
   • 计算mid；
   • 校验能否用至多k个子数组、且每个子数组和<= mid完成拆分；
   • 校验函数贪心推进：累加元素，一旦curSum > mid就新开一个子数组，并重置curSum为当前元素；
   • 若可行，记录mid为候选答案并继续搜索更小值（r = mid - 1）；否则搜索更大值（l = mid + 1）；
3. 返回最小可行值res。

代码实现

Python

class Solution: def splitArray(self, nums: List[int], k: int) -> int: def canSplit(largest): subarray = 1 curSum = 0 for num in nums: curSum += num if curSum > largest: subarray += 1 if subarray > k: return False curSum = num return True l, r = max(nums), sum(nums) res = r while l <= r: mid = l + (r - l) // 2 if canSplit(mid): res = mid r = mid - 1 else: l = mid + 1 return res

Java（对照仓库实现）

仓库中的 java/0410-split-array-largest-sum.java 采用了另一种二分写法（while (start < end)，收敛时start == end即为答案），思路完全等价：

class Solution { public int splitArray(int[] nums, int k) { int start = 0; int end = 0; for (int i = 0; i < nums.length; i++) { start = Math.max(start, nums[i]); end += nums[i]; } while (start < end) { int mid = start + (end - start) / 2; // calculate how many pieces you can divide this in with this max sum int sum = 0; int pieces = 1; for(int num : nums) { if (sum + num > mid) { sum = num; pieces++; } else { sum += num; } } if (pieces > k) { start = mid + 1; } else { end = mid; } } return end; // here start == end } }

两种写法的区别仅在于二分边界处理：l <= r写法需要额外维护res；start < end写法靠区间收敛直接得到答案，二者殊途同归。

JavaScript（对照仓库实现）

仓库中的 javascript/0410-split-array-largest-sum.js 使用位运算取中值（(left + right) >> 1），并采用"从 0 计数的 splitCount，最后用splitCount + 1 <= k判定"的等价写法：

var splitArray = function (nums, k) { let left = Math.max(...nums); let right = nums.reduce((acc, num) => acc + num, 0); let result = right; while (left <= right) { const mid = (left + right) >> 1; if (canSplit(mid)) { result = mid; right = mid - 1; } else { left = mid + 1; } } function canSplit(largest) { let splitCount = 0; let currSum = 0; for (let i = 0; i < nums.length; i++) { currSum += nums[i]; if (currSum > largest) { currSum = nums[i]; splitCount++; } } return splitCount + 1 <= k; } return result; };

Kotlin（对照仓库实现）

kotlin/0410-split-array-largest-sum.kt 的实现同样清晰直观，校验函数从subArrCnt = 1开始计数：

class Solution { fun splitArray(nums: IntArray, k: Int): Int { fun canSplit(max: Int): Boolean { var subArrCnt = 1 var curSum = 0 for (n in nums) { curSum += n if (curSum > max) { subArrCnt++ curSum = n } } return subArrCnt <= k } var l = nums.max()!! var r = nums.sum()!! var res = r while (l <= r) { val m = l + (r - l) / 2 if (canSplit(m)) { res = m r = m - 1 } else { l = m + 1 } } return res } }

Python 仓库实现（计数起点为 0 的变体）

值得留意的是，仓库中的 python/0410-split-array-largest-sum.py 将subarray从0起计数、最后用subarray + 1 <= m判定，与 JS 实现同构——这从侧面印证了"子数组计数起始值"是校验函数最容易写错的细节之一（详见后文陷阱部分）：

class Solution: def splitArray(self, nums: List[int], m: int) -> int: def canSplit(largest): subarray = 0 curSum = 0 for n in nums: curSum += n if curSum > largest: subarray += 1 curSum = n return subarray + 1 <= m l, r = max(nums), sum(nums) res = r while l <= r: mid = l + ((r - l) // 2) if canSplit(mid): res = mid r = mid - 1 else: l = mid + 1 return res

复杂度

• 时间复杂度：$O(n \log s)$ —— 二分共 $\log s$ 轮（s为数组总和），每轮校验线性扫描一遍数组；
• 空间复杂度：$O(1)$ —— 仅需常数级额外空间。

其中n为数组长度，s为数组元素总和。

这是六种方案中综合最优且最适合面试现场书写的解法：思路简洁、常数小、无需二维数组。

方案 6：二分搜索 + 前缀和优化（Binary Search + Prefix Sum）

思路

方案 5 的校验函数对每个子数组都线性累加，整体是 O(n)。借助前缀和数组，可以把"找到当前子数组最远合法终点"的过程加速：prefix[i]表示nums[0..i-1]的和，则子数组[start, end)的和为prefix[end] - prefix[start]。对每个起点，在prefix上二分出满足prefix[end] - prefix[start] <= target的最远end，从而一次跳过整个子数组。

算法步骤

1. 构建前缀和数组：prefix[i]为nums[0..i-1]的累加和（prefix[0] = 0，长度n+1）；
2. 外层仍然对答案做二分；
3. 可行性校验函数：
   • 起点i从 0 开始，在[i+1, n]上二分查找满足prefix[mid] - prefix[i] <= target的最右终点；
   • 每找到一段子数组，subarrays计数加一，i跳到该段终点；
   • 一旦subarrays > k立即返回False；
4. 返回最小可行值。

代码实现（Python）

class Solution: def splitArray(self, nums: List[int], k: int) -> int: n = len(nums) prefix = [0] * (n + 1) for i in range(n): prefix[i + 1] = prefix[i] + nums[i] def canSplit(largest): subarrays = 0 i = 0 while i < n: l, r = i + 1, n while l <= r: mid = l + (r - l) // 2 if prefix[mid] - prefix[i] <= largest: l = mid + 1 else: r = mid - 1 subarrays += 1 i = r if subarrays > k: return False return True l, r = max(nums), sum(nums) res = r while l <= r: mid = l + (r - l) // 2 if canSplit(mid): res = mid r = mid - 1 else: l = mid + 1 return res

复杂度

• 时间复杂度：$O(n + k \cdot \log n \cdot \log s)$ —— 构建前缀和 O(n)，外层二分 $\log s$ 轮，每轮校验至多形成k段、每段内部二分 O(log n)；
• 空间复杂度：$O(n)$ —— 前缀和数组。

其中n为数组长度，s为数组元素总和，k为子数组个数。

当n很大且k明显小于n时，该校验函数比方案 5 的线性扫描更省；当k接近n时二者差距不明显，实际面试中方案 5 已足够。

六种方案复杂度对比一览

常见陷阱（Common Pitfalls）

原文在最后总结了五类高频错误，每一类都在真实的面试与提交中反复出现：

陷阱一：二分边界设置错误

下界必须是max(nums)而非0或1——因为任何子数组的和都不可能小于数组中最大的单个元素（每个元素必须属于某个子数组）。上界是sum(nums)，对应所有元素合并在一个子数组的情形。边界设错会导致答案非法或二分陷入死循环。

陷阱二：子数组计数差一（Off-by-One）

校验某个目标值是否可行时，子数组计数若从0开始而非1，会"白送"一次多余的拆分机会。计数应从1开始——在发生任何切分之前，数组本身就至少构成一个子数组。仓库中的 python/0410-split-array-largest-sum.py 与 javascript/0410-split-array-largest-sum.js 使用"从 0 计数 + 最后+1判定"的等价写法，而 java/0410-split-array-largest-sum.java 与 kotlin/0410-split-array-largest-sum.kt 直接"从 1 计数"，两种写法都必须保证最终判定为"段数 ≤ k"。

陷阱三：求和过程中的整数溢出

当数组元素多且数值大时，sum(nums)、前缀和与curSum都可能溢出 32 位整数。应在前缀和与运行累加中使用long或等效的 64 位类型，避免比较结果错误、确保二分在合法数值域上运行。

陷阱四：贪心校验未正确重置当前和

校验函数中，当curSum超过目标值并开启新子数组时，curSum必须重置为当前元素本身（而不是0）。重置为0会丢掉当前元素，导致子数组计数错误——这是最容易写错的一行。

陷阱五：混淆"最小化最大值"与"最大化最小值"

本题要求最小化最大的子数组和，即寻找"仍能完成 k 段合法拆分"的最小值。如果二分方向写反（去最大化最小值），结果必然错误。二分搜索答案的第一步永远是明确：校验函数canSplit(x)对x是否单调递增，以及我们要找的是可行域的左边界还是右边界。

仓库中的实现与延伸阅读

本仓库为本题提供了四个可直接运行的多语言实现，与本文六种方案中的"二分搜索答案"一脉相承，可作为对照学习的参考样本：

• python/0410-split-array-largest-sum.py —— 二分 + 贪心校验（计数从 0 起的变体写法）；
• java/0410-split-array-largest-sum.java —— 二分区间收敛写法（start < end，无res变量）；
• javascript/0410-split-array-largest-sum.js —— 位运算取中值 + 闭包实现校验函数；
• kotlin/0410-split-array-largest-sum.kt —— 最贴近原文伪代码结构的实现。

对照阅读时建议重点关注两个细节：一是二分边界写法（l <= r+res与start < end+ 收敛）之间的等价转换；二是校验函数中子数组计数的两种起止方式（0起 + 末尾+1，与1起直接比较）。这两处细节恰好对应本文"常见陷阱"中的前两条，是理解整道题从"会写"到"写对"的关键。

另外，本题与同仓库中的 articles/capacity-to-ship-packages-within-d-days.md、articles/koko-eating-bananas.md（若存在）同属"二分搜索答案"范式，其"上下界由数据本身确定、校验函数单调、贪心验证可行域边界"的三步套路完全可以迁移复用。掌握 Split Array Largest Sum，就等于掌握了这一类"最小化最大值 / 最大化最小值"问题的通用解法模板。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode