This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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 splitnumsinto 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#### Approach #1 Brute Force [Time Limit Exceeded]

\n

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

\n

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

\n

'
\n\n

\n**Intuition**

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

\n**Algorithm**

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.

**Complexity Analysis**

- \n
- \n
Time complexity : . To split

\n`n`

elements into`m`

parts, we can have different solutions. This is equivalent to . \n - \n
Space complexity : . We only need the space to store the array.

\n \n

\n

**Intuition**

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

\nThe 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`

.

To know more about non-aftereffect property, this link may be helpful : http://www.programering.com/a/MDOzUzMwATM.html

\n**Algorithm**

Let\'s define `f[i][j]`

to be the minimum largest subarray sum for splitting `nums[0..i]`

into `j`

parts.

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.

The final answer should be `f[n][m]`

, where `n`

is the size of the array.

For corner situations, all the invalid `f[i][j]`

should be assigned with `INFINITY`

, and `f[0][0]`

should be initialized with `0`

.

**Complexity Analysis**

- \n
- \n
Time complexity : . The total number of states is . To compute each state

\n`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
Space complexity : . The space complexity is equivalent to the number of states, which is .

\n \n

\n

**Intuition**

We can easily find a property for the answer:

\n\n\nIf we can find a splitting method that ensures the maximum largest subarray sum will not exceed a value

\n`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`

.

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`

.

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.

Obviously, the specific value `x0`

is our answer.

**Algorithm**

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

.

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.

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.

**Complexity Analysis**

- \n
- \n
Time complexity : . The binary search costs , where

\n`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
Space complexity : . Same as the Brute Force approach. We only need the space to store the array.

\n \n