贪心之分割字符串

力扣410

package com.zhang.reflection.面试.算法模版.贪心算法;
import java.util.ArrayList;
/**
 * 给定一个长度为 n 的非负整数数组 num ，和一个整数 m ，你需要把这个数组 num 分成 m 个非空连续子数组。
 * 请你找出这些连续子数组各自的和的最大值最小的方案并输出这个值。
 * [1,2,3,4,5,6],3
 * 9
 * 1,2,3 为一组 4，5为一组，6为一组
 */
public class 分割数组 {
    public int splitMin (ArrayList<Integer> num, int m) {
        // write code here
        int left = 0;
        int right = 0;
        for(Integer n : num){
            left = Math.max(left, n);
            right += n;
        }
        int res = 0;
        while(left <= right){
            int mid = (left + right) / 2;
            if(ok(num, mid, m)){
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
    private boolean ok(ArrayList<Integer> nums, int mid, int m){
        int current = 0;
        for(Integer num : nums){
            if(current + num > mid){
                m--;
                current = num;
                if(m == 0){
                    return false;
                }
            } else {
                current += num;
            }
        }
        return true;
    }
}