Solution For Split Array Largest Sum

The Split Array Largest Sum problem on LeetCode asks you to divide an array of integers into m subarrays such that the maximum sum of any subarray is minimized.

For example, given the array [7,2,5,10,8] and m = 2, the optimal solution would be to split the array into [7,2,5] and [10,8], resulting in a maximum subarray sum of 12.

This problem can be solved using binary search. The range of possible answers is from the maximum value in the array (meaning each subarray only consists of one element) to the sum of all values in the array (meaning there is only one subarray). We can use binary search to find the smallest value within this range that satisfies the given conditions.

To do so, we can first calculate the middle value of the range. We then try to split the array into m subarrays such that each subarray has a sum less than or equal to the middle value. If we successfully split the array into m subarrays and each subarray has a sum less than or equal to the middle value, we can narrow the search range to the lower half of the range. If we cannot successfully split the array into m subarrays with sums less than or equal to the middle value, we need to increase the middle value and try again.

As an illustration, let’s look at the previous example: given the array [7,2,5,10,8] and m = 2, the range of possible answers is from the maximum value in the array (10) to the sum of all values in the array (32). We first calculate the middle value, which is (10+32)/2 = 21. We then try to split the array into 2 subarrays such that each subarray has a sum less than or equal to 21. One possible split is [7,2,5] and [10,8], resulting in subarray sums of 14 and 18, respectively. Since both subarrays have sums less than or equal to 21, we can narrow the search range to the lower half of the range (since we are looking for the smallest value that satisfies the conditions). We can repeat this process until we find the optimal solution.

Here is the Python code that implements the above algorithm:

“`
def splitArray(nums, m):
# calculate the range of possible answers
left = max(nums)
right = sum(nums)

# helper function to check if a middle value is valid
def is_valid(mid):
    count, total = 1, 0
    for num in nums:
        total += num
        if total > mid:
            count += 1
            total = num
            if count > m:
                return False
    return True

# binary search to find the optimal solution
while left < right:
    mid = left + (right - left) // 2
    if is_valid(mid):
        right = mid
    else:
        left = mid + 1

return left

“`

The time complexity of this solution is O(n*log(sum(nums))), where n is the length of the array and sum(nums) is the sum of all values in the array. The space complexity is O(1).

Step by Step Implementation For Split Array Largest Sum

class Solution {
    public int splitArray(int[] nums, int m) {
        int max = 0; long sum = 0;
        for (int num : nums) {
            max = Math.max(num, max);
            sum += num;
        }
        if (m == 1) return (int)sum;
        long l = max; long r = sum;
        while (l <= r) {
            long mid = (l + r)/ 2;
            if (valid(mid, nums, m)) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return (int)l;
    }
    public boolean valid(long target, int[] nums, int m) {
        int count = 1;
        long total = 0;
        for(int num : nums) {
            total += num;
            if (total > target) {
                total = num;
                count++;
                if (count > m) {
                    return false;
                }
            }
        }
        return true;
    }
}

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        # we use binary search to find the answer
        # the possible range for the answer is between the largest and smallest element in the array
        # we keep track of the mid element and see if it's possible to split the array into m subarrays 
        # such that the sum of each subarray is less than or equal to mid
        # if it's possible, then we know that the answer is less than or equal to mid
        # if it's not possible, then we know that the answer is greater than mid
        # we keep doing this until we find the answer
        
        left = max(nums)
        right = sum(nums)
        
        while left < right:
            mid = (left + right) // 2
            if self.is_possible(nums, m, mid):
                right = mid
            else:
                left = mid + 1
        
        return left
    
    def is_possible(self, nums, m, target):
        # we keep track of the current sum and the number of subarrays
        # we iterate through the array and keep adding elements to the current sum
        # if the current sum is greater than the target, then we start a new subarray
        # and reset the current sum
        # if we have more than m subarrays at the end, then it's not possible to split the array
        # into m subarrays such that the sum of each subarray is less than or equal to target
        
        curr_sum = 0
        subarrays = 1
        
        for num in nums:
            curr_sum += num
            if curr_sum > target:
                subarrays += 1
                curr_sum = num
            
            if subarrays > m:
                return False
        
        return True

/**
 * @param {number} m
 * @param {number} nums
 * @return {number}
 */
 
 //Brute force solution
var splitArray = function(nums, m) {
    //if m is 1, then the largest sum is the sum of the entire array
    if(m === 1) return nums.reduce((a, b) => a + b, 0);
    
    //indicates the minimum largest sum that can be achieved
    let min = nums.reduce((a, b) => a + b, 0);
    
    //indicates the maximum largest sum that can be achieved
    let max = nums.reduce((a, b) => a + b, 0);
    
    //while the minimum is less than the maximum, keep searching for the largest sum
    while(min < max) {
        let mid = Math.floor((min + max) / 2);
        
        //if the largest sum is less than or equal to the mid, keep searching for a larger sum
        if(canSplit(nums, m, mid)) {
            min = mid + 1;
        }
        //if the largest sum is greater than the mid, keep searching for a smaller sum
        else {
            max = mid;
        }
    }
    
    //return the largest sum
    return min;
};

//helper function to determine if a given array can be split into m subarrays with each subarray's sum being less than or equal to target
var canSplit = function(nums, m, target) {
    let sum = 0;
    let count = 1;
    
    //iterate through each element in the array
    for(let i = 0; i < nums.length; i++) {
        //add the element to the current sum
        sum += nums[i];
        
        //if the current sum is greater than the target, reset the current sum and increment the count
        if(sum > target) {
            sum = nums[i];
            count++;
            
            //if the count is greater than m, return false because the array cannot be split into m subarrays with each subarray's sum being less than or equal to target
            if(count > m) return false;
        }
    }
    
    //return true because the array can be split into m subarrays with each subarray's sum being less than or equal to target
    return true;
};

class Solution {
public:
    int splitArray(vector& nums, int m) {
        int n = nums.size();
        vector sums(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            sums[i + 1] = sums[i] + nums[i];
        }
        vector> dp(m + 1, vector(n + 1, INT_MAX));
        dp[0][0] = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = i - 1; k < j; ++k) {
                    dp[i][j] = min(dp[i][j], max(dp[i - 1][k], sums[j] - sums[k]));
                }
            }
        }
        return dp[m][n];
    }
};

public int SplitArray(int[] nums, int m) { // edge case if (nums == null || nums.Length == 0) return 0; // dp array int n = nums.Length; int[,] dp = new int[n,m]; // fill first row dp[0,0] = nums[0]; for (int i = 1; i < n; i++) { dp[i,0] = dp[i-1,0] + nums[i]; } // fill first column for (int j = 0; j < m; j++) { dp[0,j] = nums[0]; } // fill rest of the array for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { dp[i,j] = int.MaxValue; for (int k = 0; k < i; k++) { int sum = dp[k,j-1] + nums[i]; if (sum > dp[i,j]) break; dp[i,j] = Math.Min(dp[i,j], sum); } } return dp[n-1,m-1]; }