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
我们首先来分析,如果m和数组nums的个数相等,那么每个数组都是一个子数组,所以返回nums中最大的数字即可,
如果m为1,那么整个nums数组就是一个子数组,返回nums所有数字之和,所以对于其他有效的m值,返回的值必定在上面两个值之间,所以我们可以用二分搜索法来做。
我们用一个例子来分析,nums = [1, 2, 3, 4, 5], m = 3,我们将left设为数组中的最大值5,right设为数字之和15,然后我们算出中间数为10,
我们接下来要做的是找出和最大且小于等于10的子数组的个数,[1, 2, 3, 4], [5],可以看到我们无法分为3组,说明mid偏大,所以我们让right=mid,
然后我们再次进行二分查找哦啊,算出mid=7,再次找出和最大且小于等于7的子数组的个数,[1,2,3], [4], [5],我们成功的找出了三组,
说明mid还可以进一步降低,我们让right=mid,然后我们再次进行二分查找哦啊,算出mid=6,再次找出和最大且小于等于6的子数组的个数,
[1,2,3], [4], [5],我们成功的找出了三组,我们尝试着继续降低mid,我们让right=mid,然后我们再次进行二分查找哦啊,算出mid=5,
再次找出和最大且小于等于5的子数组的个数,[1,2], [3], [4], [5],发现有4组,此时我们的mid太小了,应该增大mid,我们让left=mid+1,
此时left=6,right=5,循环退出了,我们返回left即可
*/

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
*/