分割数组的最大值

题目：力扣

解题思路：动态规划和二分查找

具体可看https://leetcode-cn.com/problems/split-array-largest-sum/solution/fen-ge-shu-zu-de-zui-da-zhi-by-leetcode-solution/

 关于二分法，cnt为什么初始化为1？

这里cnt初始化为1, 是因为循环中当cnt+1的时候，首先预示着已经填满了一个子组，其次还预示着下一组已经有一个数字加入了(即total=num)，所以最后一组在循环中一定不会被记入cnt就跳出了for循环，所以要先记入一次cnt=1。

class Solution {
    //动态规划
    public int splitArray(int[] nums, int m) {
        int len = nums.length;
        int[] sub = new int[len+1];
        sub[0] = nums[0];
        //sub[i]表示从nums[0]到nums[i-1]的和，sub[j]-sub[i]表示从i到j的和
        for(int i = 0; i < len ; i++){
            sub[i+1] = nums[i] + sub[i];
        }
        //f(i,j) = min(max(f(k,j-1),sub[i]-sub[k]))
        int[][] dp = new int[len+1][m+1];
        for(int i = 0; i <= len; i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        for(int i = 1; i <= len; i++){
            for(int j = 1; j <= Math.min(i,m); j++){
                for(int k = 0; k < i; k++){
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j-1], sub[i]-sub[k]));
                }
            }
        }
        return dp[len][m];
    }
    //二分法
    public int splitArray(int[] nums, int m) {
        int left = -1;
        int right = 0;
        for(int i = 0; i < nums.length; i++){
            right = right + nums[i];
            if(nums[i]>left){
                left = nums[i];
            }
        }
        while(left < right){
            int mid = (right-left)/2 + left;
            if(check(nums, mid, m)){
                right = mid;
            }
            else{
                left = mid+1;
            }
        }
        return left;
    }
    public boolean check(int[] nums, int val, int m){
        // 这里cnt初始化为1, 是因为循环中当cnt+1的时候，首先预示着已经填满了一个子组，其次还预示着下一组已经有一个数字加入了(即total=num)，所以最后一组在循环中一定不会被记入cnt就跳出了for循环，所以要先记入一次cnt=1。
        int cnt = 1;
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            if(sum+nums[i] > val){
                cnt++;
                sum = nums[i];
            }
            else{
                sum = sum + nums[i];
            }
        }
        return cnt <= m;
    }
}