##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/410.html

# 410. Split Array Largest Sum (Hard)

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.


Companies:

Related Topics:
Binary Search, Dynamic Programming

## Solution 1. DP

Let dp[m][i] be the answer to the subproblem with m subarrays within A[0..i].

Let sum[i][j] be the sum of numbers in A[i..j].

dp[1][i] = sum[0][i]
dp[k][i] = min(max(dp[k-1][j-1], sum[j][i]) | m - 1 <= j <= i)

// OJ: https://leetcode.com/problems/split-array-largest-sum/
// Time: O(N^2 * M)
// Space: O(N^2 + NM)
class Solution {
typedef long long LL;
public:
int splitArray(vector<int>& A, int M) {
int N = A.size();
vector<vector<LL>> sum(N, vector<LL>(N, 0)), dp(M + 1, vector<LL>(N, INT_MAX));
for (int i = 0; i < N; ++i) {
LL s = 0;
for (int j = i; j < N; ++j) {
sum[i][j] = (s += A[j]);
}
}
for (int i = 0; i < N; ++i) dp[1][i] = sum[0][i];
for (int m = 2; m <= M; ++m) {
for (int i = m - 1; i < N; ++i) {
for (int j = m - 1; j <= i; ++j) {
dp[m][i] = min(dp[m][i], max(dp[m - 1][j - 1], sum[j][i]));
}
}
}
return dp[M][N - 1];
}
};


## Solution 2. DP

We can compute sum on the fly.

// OJ: https://leetcode.com/problems/split-array-largest-sum/
// Time: O(N^2 * M)
// Space: O(NM)
class Solution {
typedef long long LL;
public:
int splitArray(vector<int>& A, int M) {
int N = A.size();
vector<vector<LL>> dp(M + 1, vector<LL>(N, INT_MAX));
LL s = 0;
for (int i = 0; i < N; ++i) dp[1][i] = (s += A[i]);
for (int m = 2; m <= M; ++m) {
for (int i = m - 1; i < N; ++i) {
LL sum = 0;
for (int j = i; j >= m - 1; --j) {
sum += A[j];
dp[m][i] = min(dp[m][i], max(dp[m - 1][j - 1], sum));
}
}
}
return dp[M][N - 1];
}
};


## Solution 3. DP + Space Optimization

Given the dp dependency, we can just use 1D dp array.

// OJ: https://leetcode.com/problems/split-array-largest-sum/
// Time: O(N^2 * M)
// Space: O(N)
class Solution {
typedef long long LL;
public:
int splitArray(vector<int>& A, int M) {
int N = A.size();
vector<LL> dp(N, INT_MAX);
LL s = 0;
for (int i = 0; i < N; ++i) dp[i] = (s += A[i]);
for (int m = 2; m <= M; ++m) {
for (int i = N - 1; i >= m - 1; --i) {
LL sum = 0;
dp[i] = INT_MAX;
for (int j = i; j >= m - 1; --j) {
sum += A[j];
dp[i] = min(dp[i], max(dp[j - 1], sum));
}
}
}
return dp[N - 1];
}
};


The answer is between the maximum element and the sum of all the elements.

// OJ: https://leetcode.com/problems/split-array-largest-sum/
// Time: O(N * log(S)) where S is sum of nums.
// Space: O(1)
// Ref: https://discuss.leetcode.com/topic/61324/clear-explanation-8ms-binary-search-java
class Solution {
typedef long long LL;
int split(vector<int> &A, LL M) {
LL cnt = 0, sum = 0;
for (int i = 0; i < A.size(); ++i) {
sum += A[i];
if (sum > M) {
sum = A[i];
++cnt;
}
}
return cnt + 1;
}
public:
int splitArray(vector<int>& A, int m) {
LL sum = accumulate(begin(A), end(A), (LL)0);
if (m == 1) return sum;
LL L = *max_element(begin(A), end(A)), R = sum;
while (L <= R) {
LL M = (L + R) / 2;
int n = split(A, M);
if (n <= m) R = M - 1;
else L = M + 1;
}
return L;
}
};

• class Solution {
public int splitArray(int[] nums, int m) {
int length = nums.length;
int[][] dp = new int[length + 1][m + 1];
int[] subSum = new int[length + 1];
for (int i = 0; i <= length; i++) {
for (int j = 0; j <= m; j++)
dp[i][j] = Integer.MAX_VALUE;
}
for (int i = 0; i < length; i++)
subSum[i + 1] = subSum[i] + nums[i];
dp[0][0] = 0;
for (int i = 1; i <= length; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k < i; k++)
dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], subSum[i] - subSum[k]));
}
}
return dp[length][m];
}
}

############

class Solution {
public int splitArray(int[] nums, int k) {
int left = 0, right = 0;
for (int x : nums) {
left = Math.max(left, x);
right += x;
}
while (left < right) {
int mid = (left + right) >> 1;
if (check(nums, mid, k)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}

private boolean check(int[] nums, int mx, int k) {
int s = 1 << 30, cnt = 0;
for (int x : nums) {
s += x;
if (s > mx) {
++cnt;
s = x;
}
}
return cnt <= k;
}
}

• // OJ: https://leetcode.com/problems/split-array-largest-sum/
// Time: O(N * log(S)) where S is sum of nums.
// Space: O(1)
// Ref: https://discuss.leetcode.com/topic/61324/clear-explanation-8ms-binary-search-java
class Solution {
public:
int splitArray(vector<int>& A, int m) {
long sum = accumulate(begin(A), end(A), 0L);
if (m == 1) return sum;
long L = *max_element(begin(A), end(A)), R = sum, N = A.size();
auto valid = [&](int maxSum) {
int cnt = 1, i = 0 ;
for (int sum = 0; i < N && cnt <= m; ++i) {
sum += A[i];
if (sum > maxSum) {
sum = A[i];
++cnt;
}
}
return i == N && cnt <= m;
};
while (L <= R) {
long M = L + (R - L) / 2;
if (valid(M)) R = M - 1;
else L = M + 1;
}
return L;
}
};

• class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
def check(x):
s, cnt = 0, 1
for num in nums:
if s + num > x:
cnt += 1
s = num
else:
s += num
return cnt <= m

left, right = max(nums), sum(nums)
while left < right:
mid = (left + right) >> 1
if check(mid):
right = mid
else:
left = mid + 1
return left

############

class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""

def valid(nums, target, m):
count = 1
total = 0
for num in nums:
total += num
if total > target:
count += 1
total = num
if count > m:
return False
return True

start, end = max(nums), sum(nums)
mid = 0
while start <= end:
mid = start + (end - start) / 2
if valid(nums, mid, m):
end = mid - 1
else:
start = mid + 1

return start


• func splitArray(nums []int, k int) int {
left, right := 0, 0
for _, x := range nums {
left = max(left, x)
right += x
}
return left + sort.Search(right-left, func(mx int) bool {
mx += left
s, cnt := 1<<30, 0
for _, x := range nums {
s += x
if s > mx {
s = x
cnt++
}
}
return cnt <= k
})
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

• function splitArray(nums: number[], k: number): number {
let left = 0;
let right = 0;
for (const x of nums) {
left = Math.max(left, x);
right += x;
}
const check = (mx: number) => {
let s = 1 << 30;
let cnt = 0;
for (const x of nums) {
s += x;
if (s > mx) {
s = x;
++cnt;
}
}
return cnt <= k;
};
while (left < right) {
const mid = (left + right) >> 1;
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}