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

b'
\n\n

#### Approach #1 Brute Force [Time Limit Exceeded]

\n

Intuition

\n

Check all possible splitting plans to find the minimum largest value for subarrays.

\n

Algorithm

\n

We can use depth-first search to generate all possible splitting plan. For each element in the array, we can choose to append it to the previous subarray or start a new subarray starting with that element (if the number of subarrays does not exceed `m`). The sum of the current subarray can be updated at the same time.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . To split `n` elements into `m` parts, we can have different solutions. This is equivalent to .

\n
• \n
• \n

Space complexity : . We only need the space to store the array.

\n
• \n
\n
\n

#### Approach #2 Dynamic Programming [Accepted]

\n

Intuition

\n

The problem satisfies the non-aftereffect property. We can try to use dynamic programming to solve it.

\n

The non-aftereffect property means, once the state of a certain stage is determined, it is not affected by the state in the future. In this problem, if we get the largest subarray sum for splitting `nums[0..i]` into `j` parts, this value will not be affected by how we split the remaining part of `nums`.

\n

\n

Algorithm

\n

Let\'s define `f[i][j]` to be the minimum largest subarray sum for splitting `nums[0..i]` into `j` parts.

\n

Consider the `j`th subarray. We can split the array from a smaller index `k` to `i` to form it. Thus `f[i][j]` can be derived from `max(f[k][j - 1], nums[k + 1] + ... + nums[i])`. For all valid index `k`, `f[i][j]` should choose the minimum value of the above formula.

\n

The final answer should be `f[n][m]`, where `n` is the size of the array.

\n

For corner situations, all the invalid `f[i][j]` should be assigned with `INFINITY`, and `f` should be initialized with `0`.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . The total number of states is . To compute each state `f[i][j]`, we need to go through the whole array to find the optimum `k`. This requires another loop. So the total time complexity is .

\n
• \n
• \n

Space complexity : . The space complexity is equivalent to the number of states, which is .

\n
• \n
\n
\n

#### Approach #3 Binary Search + Greedy [Accepted]

\n

Intuition

\n

We can easily find a property for the answer:

\n
\n

If we can find a splitting method that ensures the maximum largest subarray sum will not exceed a value `x`, then we can also find a splitting method that ensures the maximum largest subarray sum will not exceed any value `y` that is greater than `x`.

\n
\n

Lets define this property as `F(x)` for the value `x`. `F(x)` is true means we can find a splitting method that ensures the maximum largest subarray sum will not exceed `x`.

\n

From the discussion above, we can find out that for `x` ranging from `-INFINITY` to `INFINITY`, `F(x)` will start with false, then from a specific value `x0`, `F(x)` will turn to true and stay true forever.

\n

Obviously, the specific value `x0` is our answer.

\n

Algorithm

\n

We can use Binary search to find the value `x0`. Keeping a value `mid = (left + right) / 2`. If `F(mid)` is false, then we will search the range `[mid + 1, right]`; If `F(mid)` is true, then we will search `[left, mid - 1]`.

\n

For a given `x`, we can get the answer of `F(x)` using a greedy approach. Using an accumulator `sum` to store the sum of the current processing subarray and a counter `cnt` to count the number of existing subarrays. We will process the elements in the array one by one. For each element `num`, if `sum + num <= x`, it means we can add `num` to the current subarray without exceeding the limit. Otherwise, we need to make a cut here, start a new subarray with the current element `num`. This leads to an increment in the number of subarrays.

\n

After we have finished the whole process, we need to compare the value `cnt` to the size limit of subarrays `m`. If `cnt <= m`, it means we can find a splitting method that ensures the maximum largest subarray sum will not exceed `x`. Otherwise, `F(x)` should be false.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . The binary search costs , where `sum of array` is the sum of elements in `nums`. For each computation of `F(x)`, the time complexity is since we only need to go through the whole array.

\n
• \n
• \n

Space complexity : . Same as the Brute Force approach. We only need the space to store the array.

\n
• \n
\n
'