如何修改最小化最大子数组和算法以实现最大化最小子数组和？

给定整数数组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;
    }
}

原算法通过二分查找求解「最小化的最大子数组和」，核心是判断当子数组最大和为mid时，所需分割数是否≤m。要改为求解「最大化的最小子数组和」，需从以下几点调整：

1. 二分边界重置 #

• low：设为数组中的最小值（子数组至少包含一个元素，最小和的最大值不会小于单个元素的最小值）；
• high：设为数组的总和（当k=1时，唯一子数组的和就是总和，即最小和的最大值）。

2. 二分搜索方向调整 #

原算法是找最小的可行mid，因此找到可行值后会尝试更小的mid；现在我们要找最大的可行mid，找到可行值后需尝试更大的mid，不可行时再缩小范围。

3. 判断函数改写 #

将原判断「子数组最大和为mid时的分割数」改为判断「能分割出多少个和≥mid的子数组」，若数量≥k，说明当前mid可行（可通过合并子数组得到恰好k个，且每个子数组和仍≥mid）。

修改后的完整代码 #

class Solution {
    int[] nums;
    public int splitArrayMaxMinSum(int[] nums, int k) {
        this.nums = nums;
        int low = Integer.MAX_VALUE;
        int high = 0;
        int maxResult = 0;
        
        // 初始化二分边界
        for (int num : nums) {
            low = Math.min(low, num);
            high += num;
        }
        
        while (low <= high) {
            // 避免整数溢出的写法
            int mid = low + (high - low) / 2;
            if (isValid(mid, k)) {
                // 当前mid可行，尝试更大的值
                maxResult = mid;
                low = mid + 1;
            } else {
                // 当前mid不可行，尝试更小的值
                high = mid - 1;
            }
        }
        return maxResult;
    }
    
    private boolean isValid(int mid, int k) {
        int count = 0;
        int currentSum = 0;
        for (int num : nums) {
            currentSum += num;
            // 累加和≥mid时，完成一个符合要求的子数组
            if (currentSum >= mid) {
                count++;
                currentSum = 0;
            }
        }
        // 若能分割出≥k个符合要求的子数组，说明mid可行
        return count >= k;
    }
}

内容的提问来源于stack exchange，提问作者learner26