NeetCode #297LC-410HardBinary SearchNC 250
← Back to All Problems#297 · #410 · Split Array Largest Sum(分割数组的最大值)
📌 Problem Statement & Constraints
Given an array
nums of non-negative integers and an integer k, split the array into k non-empty contiguous subarrays so that the largest subarray sum is minimised. Return that minimum largest sum. Constraints: 1 <= nums.length <= 1000, 0 <= nums[i] <= 10^6, 1 <= k <= min(50, nums.length).💡 Core Algorithmic Approaches
- Binary search on the answer: the predicate "can split into at most
kparts each with sum at mostc" is monotone inc. - The lower bound is
max(nums)(a single element must fit) and the upper bound issum(nums). - For a given
c, greedily accumulate until adding the next element would exceedc, then start a new part. - If the number of parts is at most
k, the capacity is feasible.
💻 Benchmark Python3 Implementation
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo + hi) // 2
parts = 1
cur = 0
for x in nums:
if cur + x > mid:
parts += 1
cur = 0
cur += x
if parts <= k:
hi = mid # feasible -> try smaller
else:
lo = mid + 1
return lo⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log(sum(nums))): each predicate is O(n).
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Using DP instead: the DP is O(n^2 * k) and much more code; the binary-search-on-answer approach is O(n log V).
- Setting the lower bound to 0: a part must contain at least one element, so
max(nums)is the tight lower bound. - Using
parts < kinstead ofparts <= k: using fewer parts thankis acceptable (extra parts can be split further), so the condition is<=. - Forgetting that subarrays must be contiguous: that is exactly why the greedy works.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Binary Search Problems
中文速览与面试要点
分割数组的最大值
给定一个非负整数数组 nums 和一个整数 k,你需要将这个数组分成 k 个 非空 的连续子数组。设计一个算法使得这 k 个子数组各自和的最大值 最小 。返回这个最小的最大值。约束:1 ≤ nums.length ≤ 1000;0 ≤ nums[i] ≤ 10^6;1 ≤ k ≤ min(50, nums.length)。
核心要点
- 二分答案(标准解) :二分「子数组和的上限 limit」,判定「能否用不超过 limit 的容量把数组分成 ≤ k 段」。
- 单调性 :limit 越大越容易满足(段数越少),因此可以二分。
- 判定函数 :贪心累加,超过 limit 就开新段。返回段数是否 ≤ k。
- 答案范围 : [max(nums), sum(nums)] 。下界是单个元素的最大值,上界是整个数组的和。
- 与 1011 完全同构 :本题是「在 D 天内送达」的抽象版本,判定函数几乎一致。
常见陷阱
- 下界写成 0 或 1 :nums[i] 可以为 0,但下界仍应取 max(nums) (保证单元素能放进一段)。
- 判定条件写成 == k :贪心得到的段数是「在 limit 下的最少段数」,若它 ≤ k,则总可以通过进一步切分得到恰好 k 段(因为允许空?不,题目要求非空段——但段数更少时可以继续切分,只要段数 ≤ k 且元素数 ≥ k 即可,题目约束保证了这一点)。因此判定应为 <= k 。
- 用 DP 求解 : dp[i][j] 表示前 i 个元素分成 j 段的最小最大值,复杂度 O(n² k)。n = 1000 时约 5 × 10^7,可能超时;二分答案只需 O(n log(sum))。
- 二分方向写反 :本题求「最小的最大和」,应写 if feasible: r = mid 。
参考实现
class Solution:
def splitArray(self, nums: list[int], k: int) -> int:
def segments_needed(limit: int) -> int:
cnt = 1
cur = 0
for x in nums:
if cur + x > limit:
cnt += 1
cur = 0
cur += x
return cnt
l, r = max(nums), sum(nums)
while l < r:
mid = (l + r) // 2
if segments_needed(mid) <= k:
r = mid # 可行 -> 尝试更小的上限
else:
l = mid + 1
return l