# 410. Split Array Largest Sum

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.

&#x20;

**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
```

&#x20;

**Constraints:**

* `1 <= nums.length <= 1000`
* `0 <= nums[i] <= 106`
* `1 <= m <= min(50, nums.length)`
* `1 <= nums.length <= 1000`
* `0 <= nums[i] <= 106`
* `1 <= m <= min(50, nums.length)`

**Constraints:**

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

## Solution

The question is to find the maximum range sum among m subRanges. And we require to let the sum of each range be as small as possible.

That is the given maximum range sum k; all the range sum shall be small or equal to this sum.\
Then if we split the original array with k,  it must be able to split the array into m subRanges.

Thus, a binary search approach can be applied. Given that if the k is fulfilled requirement, the subRanges number must be equal to m. if the number is less than m, it means the k is too big, if the number is larger than m, then the k is too small.

We can apply binary search to find the smallest one k let the number of sumRange >= m;

```java
 public int splitArray(int[] nums, int m) {
        int min = 0, max = 0;
        for(int num : nums){
            min = Math.max(min, num);
            max += num;
        }
        
        while(max > min){
            int mid = min + (max-min)/2;
            if(isfeasible(mid, nums, m)){
                max = mid;
            }
            else{
                min = mid+1;
            }
        }
        return min;
    }
    
    public boolean isfeasible(int threshold, int[] nums, int m){
        int count = 1;
        int curSum = 0;
        for(int num : nums){
            curSum += num;
            if(curSum > threshold){
                count++;
                curSum = num;
            }
        }
        return count <= m;
    }
```
