分割陣列的最大值問題

作者：Grey

原文地址：

部落格園：分割陣列的最大值問題

CSDN：分割陣列的最大值問題

題目說明

給定一個非負整數陣列 nums 和一個整數 m ，你需要將這個陣列分成 m 個非空的連續子陣列。設計一個演演算法使得這 m 個子陣列各自和的最大值最小。

線上測評見：LeetCode 410. Split Array Largest Sum

主要思路

我們先求整個陣列的累加和，假設累加和為 sum，我們可以得到一個結論：

分割的 m 個非空連續子陣列，每個陣列內元素之和的範圍一定在(0,sum]區間內。

如果某種劃分下的子陣列之和的最大值為 max，則 max 首先肯定在(0,sum]區間內。

所以我們可以嘗試將思路轉換為：

我們先設定一個 max，子陣列的累加和最大值不能超過 max 的情況下，最少可分多少部分？

假設能分 k 個部分，

如果k <= m，說明設定的 max 這種劃分是滿足條件的，再看 max 是否可以變的更小。

如果k > m，說明設定的 max 這種劃分是不滿足條件的，需要調大 max 的值。

我們可以通過二分的方式來定位 max 的值。即 max 先取(0,sum]的中點值，得到的劃分部分數量為 k，如果k <= m，則 max 繼續去左邊取中點位置來得到新的劃分 k，

如果k > m，max 繼續從右邊的中點位置來得到新的劃分 k 。

完整程式碼

class Solution {
    public static int splitArray(int[] nums, int m) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int l = 0;
        int r = sum;
        int ans = 0;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            int parts = getParts(nums, mid);
            if (parts > m) {
                // mid越大，parts才會越小
                l = mid + 1;
            } else {
                ans = mid;
                r = mid - 1;
            }
        }
        return ans;
    }

    // 達到aim要分幾部分
    public static int getParts(int[] nums, int aim) {
        for (int num : nums) {
            if (num > aim) {
                return Integer.MAX_VALUE;
            }
        }
        int part = 1;
        int all = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (all + nums[i] > aim) {
                part++;
                all = nums[i];
            } else {
                all += nums[i];
            }
        }
        return part;
    }
}

其中：int getParts(int[] nums, int aim)方法表示：

在連續子陣列之和不超過 aim 的情況下，最少需要幾個劃分部分。

方法的主要邏輯是：

遍歷陣列，

如果發現某個元素的值超過了 aim，直接返回系統最大，說明無法得到劃分。

如果沒有超過 aim，則繼續加入下一個元素，直到超過 aim，就定位出一個部分。依次類推，就可以得到最少有幾個劃分。

由於不回退機制，整個演演算法時間複雜度 O(N)。

更多地，此題也可以用四邊形不等式優化的動態規劃來解，但是最優解是二分法。

演演算法和資料結構筆記