Cacher is the code snippet organizer for pro developers

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