Split Array & Maximized Smallest Sum

Question

Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the smallest sum of any subarray is maximized. Return the maximized smallest sum of the split. Input: nums = [7,2,5,10,8], k = 2 Output: 14 I found an algorithm that finds the minimized largest sum. How to modify this algorithm so that it finds the maximized smallest sum?

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;
    }
}

Answer 1

Some things to change to achieve that:

• The binary search should now keep track of the maximized sum, so this means that instead of minimizing a variable min, you should maximize a variable max, and at the end return that value.

• When required_no_of_chunks is true, the binary search algorithm should now try lesser values instead of greater values, so that means the low, high window should be reduced in the opposite direction.

• required_no_of_chunks should now ensure that all partitions have at least the required sum. This means the inner while loop should continue (if possible) when val is still less than the required mid. It should also check that if there are no more values in the array, the last chunk also has attained this minimal sum.

Here is the adapted code with comments where changes were made:

class Solution {
    int[] nums;
    public int splitArray(int[] nums, int m) {
        this.nums = nums;
        int low = 0, high = 0, 
            max = Integer.MIN_VALUE; // adapted
        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)){
               max = Math.max(max, mid); // adapted
               low = mid + 1;  // adapted
            }
            else high = mid - 1; // adapted 
        }
        return max; // adapted
    }
    
    private boolean required_no_of_chunks(int mid, int m){
        int chunks = 0, i=0;
        while(i < nums.length && chunks < m){ // condition extended for quicker exit
            int val = 0;
            // Second part of Loop condition adapted
            while(i < nums.length && val < mid) val += nums[i++];
            // Added: give up if val is too low
            if (val < mid) return false;
            chunks++;
        }
        return true; // Simplified in view of extended loop condition
    }
}