BiruLyu
6/7/2017 - 6:28 PM

## 410. Split Array Largest Sum(Binary Search).java

``````/*
dp[i][j] = optimal solution of spliting first j elements in nums into i groups
*/
public class Solution {
public int splitArray(int[] nums, int m) {
if(nums == null || nums.length < m) return 0;
int len = nums.length;
int[] prefixSum = new int[len + 1];
for(int i = 1; i <= len; i++) {
prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
}
int[][] dp = new int[m + 1][len + 1];
for(int i = 0; i<= m; i++){
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
dp[0][0] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= len; j++) {
for(int k = i - 1; k < j; k++) {
int val = Math.max(dp[i - 1][k], prefixSum[j] - prefixSum[k]);
dp[i][j] = Math.min(dp[i][j], val);
}
}
}
return dp[m][len];

}
}``````
``````/*
http://www.cnblogs.com/grandyang/p/5933787.html

[1,2,3], [4], [5]，我们成功的找出了三组，我们尝试着继续降低mid，我们让right=mid，然后我们再次进行二分查找哦啊，算出mid=5，

*/

public class Solution {
public int splitArray(int[] nums, int m) {
if(nums == null || nums.length < m) return 0;
long left = 0;
long right = 0;
for(int num : nums) {
left = Math.max(left, num);
right += num;
}
while(left < right) {
long mid = left + (right - left) / 2;
if(canSplit(nums, m, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return (int)left;

}

private boolean canSplit(int[] nums, int m, long mid) {
int curCount = 1;
int curSum = 0;
for (int i = 0; i < nums.length; i++) {
curSum += nums[i];
if (curSum > mid) {
curSum = nums[i];
curCount++;
}
if (curCount > m) {
return false;
}
}
return true;
}
}

/*
[7,2,5,10,8]
2
[1]
2
[1]
1
[1,1]
2
[1,2,3,4,5]
5
*/``````