410. Split Array Largest Sum

Hard

Description

給定一個非負整數陣列 nums 和整數 k，將陣列分成 k 個非空連續子陣列，使得這 k 個子陣列的最大和最小化。回傳這個最小化後的最大和。

Example:

Input: nums = [7,2,5,10,8], k = 2 Output: 18（分成 [7,2,5] 和 [10,8]，最大和為 18）

Intuition#

在答案空間 [max(nums), sum(nums)] 上二分搜尋，找最小的「子陣列和上限」使得能分成 <= k 組。

「最小化最大值」– 經典的二分搜尋訊號
給定一個上限 threshold，貪心地從左到右劃分，每組和不超過 threshold
如果能分成 <= k 組，表示 threshold 可行；否則太小
與 #1011 Capacity to Ship Packages 本質上是同一題

Approaches#

1: Dynamic Programming#

概念: dp[i][j] = 前 i 個元素分成 j 組的最小最大和
時間複雜度: O(n^2 * k)
空間複雜度: O(n * k)

DP 程式碼

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#

概念: 在 [max(nums), sum(nums)] 上二分搜尋，貪心驗證是否能在上限內分成 <= k 組
時間複雜度: O(n * log(sum(nums)))
空間複雜度: 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
    }
}

這題與 #1011 Capacity to Ship Packages 幾乎相同：船的載重量 = 子陣列和上限，天數 = 分組數。理解這個對應關係後，兩題用同一個模板即可。

🔑 Takeaways#

Pattern: Binary Search on Answer + Greedy Validation（最小化最大值）
關鍵技巧: 「最小化最大值」或「最大化最小值」幾乎都可以用二分搜尋解。貪心驗證：從左到右累加，超過上限就開新一組。記住這個模式可以解一系列類似問題（#875, #1011, #410）