Split Array Largest Sum

class Solution {
public:
    int computeMinSubarrays(vector<int>& arr, int limit) {
        int sum = 0;
        int required = 0;
            
        for (int num : arr) {
            if (sum + num <= limit) {
                sum += num;
            } else {
                sum = num;
                required++;
            }
        }
            
        return required + 1;
    }
        
    int splitArray(vector<int>& arr, int m) {
        int totalSum = 0;
        int highestValue = INT_MIN;
        for (int num : arr) {
            totalSum += num;
            highestValue = max(highestValue, num);
        }
            
        int low = highestValue;
        int high = totalSum;
        int bestSmallestMax = 0;
            
        while (low <= high) {
            int mid = low + (high - low) / 2;
    
            if (computeMinSubarrays(arr, mid) <= m) {
                high = mid - 1;
                bestSmallestMax = mid;
            } else {
                low = mid + 1;
            }
        }
            
        return bestSmallestMax;
    }
};

The provided solution in C++ addresses the problem of determining the smallest possible largest sum of m subarrays into which a given array arr can be divided.

• Firstly, the program utilizes two main functions:

• computeMinSubarrays accepts an integer array arr and a limit value. It iterates over the array to determine the minimum number of subarrays needed without exceeding the given limit. This is achieved by aggregating elements until the addition of a new element would exceed the limit, at which point a new subarray is started.

• splitArray is the main function that utilizes binary search to find the optimal solution. It initializes with the largest individual element of the array as low and the sum of all elements as high, ensuring all possible sums are bracketed between these two extremes.

• The binary search repeatedly calculates the mid-value between low and high. For each mid-value, which represents a potential maximum subarray sum, computeMinSubarrays is called to check how many subarrays are required if that mid-value is the maximum sum allowed per subarray.

• If the number of subarrays required is less than or equal to m, the mid-value is a valid candidate for the answer, and high is adjusted to narrow the search range.

• Conversely, if the mid-value requires more than m subarrays, it means the mid-value is too small, and low is adjusted to search for a larger possible value.

• The binary search continues until low surpasses high, at which point the optimal smallest maximum sum of subarrays is found in bestSmallestMax.

This approach leverages the binary search algorithm for efficient determination of the required value, making the search logarithmic relative to the sum range, combined with linear checks via the computeMinSubarrays function, resulting in an efficient and effective solution.

class Solution {
    private int countSubarrays(int[] array, int limit) {
        int total = 0;
        int count = 0;
            
        for (int value : array) {
            if (total + value <= limit) {
                total += value;
            } else {
                total = value;
                count++;
            }
        }
            
        return count + 1;
    }
        
    public int splitArray(int[] array, int divisions) {
        int totalSum = 0;
        int highest = Integer.MIN_VALUE;
        for (int value : array) {
            totalSum += value;
            highest = Math.max(highest, value);
        }
            
        int lowerBound = highest;
        int upperBound = totalSum;
        int optimalMax = 0;
        while (lowerBound <= upperBound) {
            int mid = lowerBound + (upperBound - lowerBound) / 2;
                
            if (countSubarrays(array, mid) <= divisions) {
                upperBound = mid - 1;
                optimalMax = mid;
            } else {
                lowerBound = mid + 1;
            }
        }
            
        return optimalMax;
    }
}

The Java solution provided resolves the problem named "Split Array Largest Sum". This program determines the smallest sum among the largest sums of the subarrays when an array is split into a specified number of divisions. Here's a breakdown of how the solution achieves this:

• Method countSubarrays:

  • This method calculates how many subarrays are required for a given maximum subarray sum (referred to as limit).
  • It iterates through the array, summing up elements until adding another would surpass the limit. At this point, it starts a new subarray, thus tracking the number of subarrays needed for the specified limit.

• Method splitArray:

  • Uses binary search to find the minimum maximum subarray sum.
  • It first calculates the totalSum of all array elements and finds the largest single element value, highest, as potential bounds for the binary search.
  • lowerBound is set to highest and upperBound to totalSum.
  • The binary search is adjusted iteratively by recalculating the middle sum (mid) and using countSubarrays to check if the given mid can be a feasible largest sum with the allowed number of divisions.
  • The search space is narrowed based on whether the number of divisions needed is less than or equal to the allowed divisions, adjusting lowerBound and upperBound accordingly.

Finally, the method returns the optimal largest sum for the required divisions. This approach ensures efficiency by leveraging the binary search method to minimize the maximum sum required to split the array within the given constraints.

class Solution:
    def splitArray(self, numbers: List[int], partitions: int) -> int:
            
        def subarrays_needed(max_sum_limit: int) -> int:
            total_sum = 0
            required_splits = 0
                
            for num in numbers:
                if total_sum + num <= max_sum_limit:
                    total_sum += num
                else:
                    total_sum = num
                    required_splits += 1
    
            return required_splits + 1
            
        left = max(numbers)
        right = sum(numbers)
            
        while left <= right:
            mid_value = (left + right) // 2
                
            if subarrays_needed(mid_value) <= partitions:
                right = mid_value - 1
                minimum_sum = mid_value
            else:
                left = mid_value + 1
            
        return minimum_sum

The provided code addresses the problem of splitting an array into a specified number of partitions such that the maximum sum of any partition is minimized. This scenario is tackled using a binary search approach over potential sums, implementing it in Python.

• Start by defining the function splitArray with parameters for the list of integers and the number of desired partitions.
• Introduce an internal helper function subarrays_needed that calculates the number of subarrays required given a maximum sum limit. This function iterates through the numbers, building subarrays and counting them based on the given sum limit.
• Establish the initial bounds for binary search with:
  • left set as the maximum value in the numbers list, ensuring that the maximum sum cannot be lower than any single element.
  • right as the sum of all elements, representing the scenario where only one partition is used.
• Execute the binary search:
  1. Calculate the middle point between the current left and right bounds.
  2. Use the subarrays_needed function to determine the number of partitions required for the mid value as a maximum sum.
  3. If the required partitions count is within the allowed number, adjust the right boundary to search for a potentially smaller maximum sum. Store this as the current best known minimum sum.
  4. If the partition count exceeds the limit, adjust the left boundary to allow for a larger sum limit and continue the search.
• At the end of the binary search, the minimum_sum variable holds the minimized largest sum possible under the given constraints, which is returned as the function's result.

This approach efficiently narrows down the potential maximum sums, ensuring an optimal solution through the binary search methodology and careful partition counting.