> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/binary-search/410-split-array-largest-sum.md).

# 410    Split Array Largest Sum

## 410. [Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum/description/)

## 1. Question

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:**\
Ifnis 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.
```

## 2. Implementation

**(1) Binary Search**

思路：题目的本质是在这数组所有可能的m个subarray的最大sum里找一个最小的，可以利用二分法的思想，找到这个subarrat sum的左边界。做法是找出这个subarray sum的上下限，由于数组的所有元素都是非负的，所以上限就是数组总和，下限就是单独一个元素的最大值(注意，不是最小值，因为是找m个subarray里最大的一个)，在这个范围里做二分

```java
class Solution {
    public int splitArray(int[] nums, int m) {
        int low = Integer.MIN_VALUE, high = 0, mid = 0;

        for (int num : nums) {
            low = Math.max(low, num);
            high += num;
        }

        while (low + 1 < high) {
            mid = low + (high - low) / 2;

            if (!isValid(nums, m - 1, mid)) {
                low = mid + 1;
            }
            else {
                high = mid;
            }
        }
        return isValid(nums, m - 1, low) ? low : high;
    }

    public boolean isValid(int[] nums, int cuts, int target) {
        int sum = 0;
        for (int num : nums) {
            if (num > target) {
                return false;
            }

            if (sum + num <= target) {
                sum += num;
            }
            else {
                --cuts;
                sum = num;
                if (cuts < 0) {
                    return false;
                }
            }
        }
        return true;
    }
}
```

## 3. Time & Space Complexity

**Binary Search:** 时间复杂度O(nlog(maxSum - minSum + 1)), n是数组元素个数, 空间复杂度O(1)