# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/leetcode/binary-search/410-split-array-largest-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.