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.

&nbsp;
Example 1:

Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.


Example 2:

Input: nums = [1,2,3,4,5], m = 2
Output: 9


Example 3:

Input: nums = [1,4,4], m = 3
Output: 4


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 1000
	0 &lt;= nums[i] &lt;= 106
	1 &lt;= m &lt;= min(50, nums.length)


class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        lo, hi = max(nums), sum(nums)
        while lo < hi:
            mid = (lo+hi)//2
            tot, cnt = 0, 1
            for num in nums:
                if tot+num<=mid: 
                    tot += num
                else:
                    tot = num
                    cnt += 1
            if cnt>m: lo = mid+1
            else: hi = mid
        return hi
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;
    }
}
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        long long low = 0;
        long long res =0;
        long long high = 1000000005;
        while(low<=high){
            long long mid = (low+high)/2;
            int cnt = 1;
            long long current_sum = 0;
            int can = 1;
            for(auto num: nums){
                if(num > mid){
                    can = 0;
                    break;
                }
                if(current_sum+num>mid){
                    cnt ++;
                    current_sum = 0;
                }
                current_sum += num;
            }
            if(can==1){
                if(cnt>m){
                    low = mid+1;
                }
                else{
                    res = mid;
                    high = mid-1;
                }
            }
            else{
                low = mid+1;
            }
        }
        return res;
    }
};
var splitArray = function(nums, m) {
const n = nums.length;
var mat = [];
var sumArr = [nums[0]];
for(let i=1; i<n; i++){
    sumArr.push(sumArr[i-1]+nums[i]);//find prefix sum
}
mat.push(sumArr);
for(let i=0; i<n-1;i++){//form prefix matrix, i.e. every row i shows prefix sum starting from i
    let arr = new Array(n).fill(0);
    for(let j=i+1; j<n; j++){
        arr[j] = sumArr[j] - sumArr[i];
    }
    mat.push(arr);
}
let memo = new Map();
let recursion = (m,lastPartition) => {// recursive partition finder
    if(memo[m+'_'+lastPartition]!==undefined){
        return memo[m+'_'+lastPartition];//memoised
    }
    if(m==1){//base case, only 1 partition left
        memo[m+'_'+lastPartition] = mat[lastPartition][mat[0].length-1];
        return memo[m+'_'+lastPartition];
    }
    let min = Infinity;
    let maxSum = -Infinity;
    let lastval = Infinity;
    for(let i = lastPartition; i<=n-m; i++){//for mth partition, find the min sum for all possible partition placements
        while(i>0 && i<n-m && mat[lastPartition][i] == lastval) i++;//if a large set of values are repeating, i.e. a lot of 0s in original array, skip them
        lastval = mat[lastPartition][i];
        maxSum = Math.max(mat[lastPartition][i],recursion(m-1,i+1));//max of current subarray sum with max from the rest of the partitions
        min = Math.min(min, maxSum);//minimum sum for all the possible partition values
    }
    memo[m+'_'+lastPartition] = min;
    return memo[m+'_'+lastPartition];
}
return recursion(m,0);
};
Split Array Largest Sum