給定一個非負整數陣列
nums和整數k，將陣列分成k個非空連續子陣列，使得這k個子陣列的最大和最小化。回傳這個最小化後的最大和。
Example:
Input: nums = [7,2,5,10,8], k = 2 Output: 18（分成 [7,2,5] 和 [10,8]，最大和為 18）
Intuition
TIP
在答案空間 [max(nums), sum(nums)] 上二分搜尋，找最小的「子陣列和上限」使得能分成 <= k 組。
- 「最小化最大值」— 經典的二分搜尋訊號
- 給定一個上限
threshold，貪心地從左到右劃分，每組和不超過 threshold - 如果能分成 <= k 組，表示 threshold 可行；否則太小
- 與 #1011 Capacity to Ship Packages 本質上是同一題
Approaches
1. Dynamic Programming — O(n^2 * k) / O(n * k)
- Idea:
dp[i][j]= 前 i 個元素分成 j 組的最小最大和 - Time:
O(n^2 * k) - Space:
O(n * k)
DP Code
class Solution {
fun splitArray(nums: IntArray, k: Int): Int {
val n = nums.size
val prefix = LongArray(n + 1)
for (i in nums.indices) {
prefix[i + 1] = prefix[i] + nums[i]
}
// dp[i][j] = 前 i 個元素分成 j 組的最小最大和
val dp = Array(n + 1) { IntArray(k + 1) { Int.MAX_VALUE } }
dp[0][0] = 0
for (i in 1..n) {
for (j in 1..minOf(i, k)) {
for (prev in j - 1 until i) {
val sum = (prefix[i] - prefix[prev]).toInt()
dp[i][j] = minOf(dp[i][j], maxOf(dp[prev][j - 1], sum))
}
}
}
return dp[n][k]
}
}⭐ 2. Binary Search on Answer + Greedy — O(n * log(sum(nums))) / O(1)
- Idea: 在 [max(nums), sum(nums)] 上二分搜尋，貪心驗證是否能在上限內分成 <= k 組
- Time:
O(n * log(sum(nums))) - Space:
O(1)
class Solution {
fun splitArray(nums: IntArray, k: Int): Int {
var left = nums.max().toLong()
var right = nums.sumOf { it.toLong() }
while (left < right) {
val mid = left + (right - left) / 2
if (canSplit(nums, k, mid)) {
right = mid
} else {
left = mid + 1
}
}
return left.toInt()
}
private fun canSplit(nums: IntArray, k: Int, threshold: Long): Boolean {
var groups = 1
var currentSum = 0L
for (num in nums) {
if (currentSum + num > threshold) {
groups++
currentSum = num.toLong()
if (groups > k) return false
} else {
currentSum += num
}
}
return true
}
}WARNING
這題與 #1011 Capacity to Ship Packages 幾乎相同：船的載重量 = 子陣列和上限，天數 = 分組數。理解這個對應關係後，兩題用同一個模板即可。
🔑 Takeaways
- Pattern: Binary Search on Answer + Greedy Validation（最小化最大值）
- Key trick: 「最小化最大值」或「最大化最小值」幾乎都可以用二分搜尋解。貪心驗證：從左到右累加，超過上限就開新一組。記住這個模式可以解一系列類似問題（#875, #1011, #410）