> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/binary-searching-and-sorting/split-array-largest-sum.md).

# Split Array Largest Sum

Given an array 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.

**Note:**\
If n is the length of array, assume the following constraints are satisfied:

* 1 ≤ n ≤ 1000
* 1 ≤ m ≤ min(50, n)

**Examples:**

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

```java
class Solution {
    public int splitArray(int[] nums, int m) {
        // When every element forms it's own group
        long min = Integer.MIN_VALUE;
        // When all the elements are in one group
        long max = 0;
        for (int x : nums) {
            min = Math.max(min, x);
            max += x;
        }
        while (min < max) {
            // "mid" represents the max sum in each group
            long mid = min + (max - min) / 2;
            int groups = numberOfGroups(nums, mid);
            if (groups > m)
                min = mid + 1;
            else
                max = mid;
        }
        return (int) min;
    }

    public int numberOfGroups(int[] nums, long maxSum) {
        long currSum = 0, groups = 1;
        for (int x : nums) {
            currSum += x;
            if (currSum > maxSum) {
                currSum = x;
                groups++;
            }
        }
        return (int) groups;
    }
}
```