题解 | #分割数组#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型ArrayList 
     * @param m int整型 
     * @return int整型
     */
    public int splitMin (ArrayList<Integer> num, int m) {
        //求所有数总和,和最大数
        int sum = 0;
        int max = num.get(0);
        for(int n : num){
            sum+=n;
            max = max>n?max:n;
        }
        return getRes(num,m,max,sum);
            
    }

    private int getRes(ArrayList<Integer> num,int m,int left ,int right){
        
        int target = (left+right+1)/2;
        //从前往后遍历整个数组,sum_sub存子数组和,count存子数组的个数
        //sum_max存子数组最大和
        int sum_sub = 0;
        int count = 1;
        int sum_max = 0;
        for(int i =0;i<num.size();i++){
            if(sum_sub + num.get(i) <= target){
                sum_sub+= num.get(i);
            }else{ //子数组的和将要超过target时，分割，sum_sub重置，count+1
                sum_sub = num.get(i);
                count++;
            }
            sum_max = Math.max(sum_max,sum_sub);
        }
        System.out.println("target="+target+" sum_max="+sum_max+" count="+count+" left="+left+" right="+right);
        //遍历完成后判断count数量
        if(count > m){  //分割的多，说明不可行，target值太小
            return getRes(num,m,target,right);
        }else if(left < right-1){//分割的少，说明可行，但是有缩小空间，target值太大
            return getRes(num,m,left,target);
        }else{ // left,right正好相等，说明分割的合适，此时输出最大子数组和
           return  sum_max;
        }

    }
}