題目
#

leetcode 410 - Split Array Largest Sum(題目說明請點連結)

題目簡述
#

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

Example 1:

Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: 有四種方式將 nums 分成兩個子陣列。最好的方式是分成 [7,2,5] 和 [10,8]，其中兩個子陣列中最大的和只有 18。

Example 2:

Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: 有四種方式將 nums 分成兩個子陣列。最好的方式是分成 [1,2,3] 和 [4,5]，其中兩個子陣列中最大的和只有 9。

解題思路
#

輸入為一個字串，輸出為能切成的K群數內子集合其中最大的總和，舉例：
nums = [7,2,5,10,8] 可以被分成 k = 2 群數的子集合，
[7,2,5] 和 [10,8]，其中最大的和為18(10+8)。

我們的目標是最小化子結合的最大和（即答案），這是一個有序範圍問題，因為：

當分割數 k 增加時，每個子集合的和會減小（子集合更短）。
當分割數 k 減少時，每個子集合的和會增大（子集合更長）。

而問題可以轉化為判斷 sum 是否滿足條件，將數組劃分為 k 個子集合，且每個子集合的和都不超過 sum。
而其單調性也符合使用二分搜索的條件，二分法範圍如下：

左邊界（min）：陣列中的最大值，因為任何子集合的和都至少等於其陣列當中的最大值。
- min=max(nums)
右邊界（max）：所有數字的總和，因為當 k=1 時，所有數字都在一個子集合中。
- max=∑(nums)

二分搜索過程：

初始化二分範圍為 [min,max]。
計算中間值 mid=(min+max)/2。
建立canSplit方法驗證 mid 是否可行(其最大值mid是否能分成k群)：
- 如果可行，更新右邊界 max=mid，嘗試更小的最大和。
- 如果不可行，更新左邊界 min=mid+1。
最後當 min(left)==max(right)，找到答案

例子說明
#

nums = [7,2,5,10,8], k = 2

初始情況：left = 10（最大值），right = 32（總和）

第一次二分：mid = 21
- 檢查是否能分成 2 個子集合，每個子集合和 ≤ 21
- 可行：[7,2,5] 和 [10,8]，right = mid = 21
第二次二分：mid = 15
- 檢查是否能分成 2 個子集合，每個子集合和 ≤ 15
- 不可行，left = mid + 1 = 16
第三次二分：mid = 18
- 檢查是否能分成 2 個子集合，每個子集合和 ≤ 18
- 可行：[7,2,5] 和 [10,8]，right = mid = 18
第四次二分：mid = 17
- 檢查是否能分成 2 個子集合，每個子集合和 ≤ 17
- 不可行，left = mid + 1 = 18
最終結果：
- left = 18，返回 18

完整程式碼
#

java

class Solution {
    public int splitArray(int[] nums, int k) {
        int left = 0; // 初始化左邊界
        int right = 0; // 初始化右邊界
        for(int num : nums) { // 遍歷數組
            if(num > left) { // 找到最大值作為左邊界
                left = num;
            }
            right += num; // 累計總和作為右邊界
        }

        while(left < right) { // 當left小於right時繼續搜索
            int mid = left + (right - left) / 2; // 計算中間值
            if(canSplit(nums, k, mid)) { // 檢查是否能分成k個子集合，每個子集合和≤mid
                right = mid; // 如果可行，嘗試更小的最大和
            } else {
                left = mid + 1; // 如果不可行，嘗試更大的最大和
            }
        }

        return left; // 返回最小可行值
    }
    
    public boolean canSplit(int nums[], int k, int maxValue) {
        int sum = 0; // 當前子集合的和
        int count = 1; // 已分割的子集合數量

        for(int num : nums) { // 遍歷數組
            if(sum + num > maxValue) { // 如果加入當前數字會超過最大值
                count++; // 開始新的子集合
                sum = num; // 重置當前子集合的和

                if(count > k) { // 如果子集合數量超過k
                    return false; // 不可行
                }
            } else {
                sum += num; // 將當前數字加入當前子集合
            }
        }
        return true; // 可行
    }
}