Leetcode Split Array Largest Sum problem solution

YASH PAL,

In this Leetcode Split Array Largest Sum problem solution, You are given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Leetcode Split Array Largest Sum problem solution

Problem solution in Python.

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        dp = [[float("inf") for _ in range(len(nums))] for _ in range(m)]
        dp[0][0] = nums[0]
        for j in range(1, len(nums)):
            dp[0][j] = dp[0][j-1] + nums[j]
        
        for i in range(1,m):
            for j in range(i, len(nums)):
                dp[i][j] = min([max(dp[i-1][k],dp[0][j]-dp[0][k]) for k in range(i-1, j)])
        return dp[-1][-1]

Problem solution in Java.

class Solution {
    public int splitArray(int[] nums, int m) {
        int low = IntStream.of(nums).max().orElse(0);
        int high = IntStream.of(nums).sum();
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (split(nums, mid) > m) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
    
    private int split(int[] nums, int sum) {
        int ret = 1;
        int currentSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (currentSum + nums[i] > sum) {
                ret++;
                currentSum = 0;
            }
            currentSum += nums[i];
        }
        return ret;
    }
}

Problem solution in C++.

bool can_split(vector<int> &nums,int m,long long int sum)
    {
        long long int cnt=1,cnt_sum=0;
        for (int i = 0; i <nums.size() ; ++i) {
            cnt_sum+=nums[i];
            if(cnt_sum>sum)
            {
                cnt_sum=nums[i];
                ++cnt;
                if (cnt>m) return false;
            }
        }
        return true;
    }
    int splitArray(vector<int>& nums, int m) 
    {
        long long left=*max_element(nums.begin(),nums.end());
        long long right=accumulate(nums.begin(),nums.end(),0ll);
        while(left<right)
        {
            long long mid=(left+right)>>1;
            if(can_split(nums,m,mid)) right=mid;
            else left=mid+1;
        }
        return left;
        
    }

coding problems solutions