Split Array & Maximized Smallest Sum

问题描述 投票:0回答:0

给定一个整数数组 nums 和一个整数 k,将 nums 拆分为 k 个非空子数组,使得任意子数组的最小和最大化。 返回拆分的最大最小总和。 输入:nums = [7,2,5,10,8], k = 2 输出:14 我找到了一种算法,可以找到最小化的最大总和。 如何修改这个算法,让它找到最大的最小总和?

class Solution {
    int[] nums;
    public int splitArray(int[] nums, int m) {
        this.nums = nums;
        int low = 0, high = 0, min = Integer.MAX_VALUE;
        for(int i=0;i<nums.length;i++){
            low = Math.max(low, nums[i]);
            high += nums[i];
        }
        while(low <= high) {
            int mid = (low + high) / 2;
            if(required_no_of_chunks(mid, m)){
               min = Math.min(min, mid);
               high = mid - 1;
            }
            else low = mid + 1;
        }
        return min;
    }
    
    private boolean required_no_of_chunks(int mid, int m){
        int chunks = 0, i=0;
        while(i < nums.length){
            int val = 0;
            while(i < nums.length && nums[i] + val <= mid) val += nums[i++];
            chunks++;
        }
        return chunks <= m;
    }
}
java algorithm binary-tree
© www.soinside.com 2019 - 2024. All rights reserved.