分割數組的最大值問題
分割數組的最大值問題
作者：Grey
原文地址：
題目說明
給定一個非負整數數組 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)。
更多地，此題也可以用四邊形不等式優化的動態規劃來解，但是最優解是二分法。
