# 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:
Given  m  satisfies the following constraint: 1 ≤ m ≤ length(nums) ≤ 14,000.

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

``````class Solution {
public:
int splitArray(vector<int>& nums, int m) {
long left = 0, right = 0;
for (int i = 0; i < nums.size(); ++i) {
left = max(left, (long)nums[i]);
right += nums[i];
}
while (left < right) {
long long mid = left + (right - left) / 2;
if (can_split(nums, m, mid)) right = mid;
else left = mid + 1;
}
return right;
}
bool can_split(vector<int>& nums, long m, long sum) {
long cnt = 1, curSum = 0;
for (int i = 0; i < nums.size(); ++i) {
curSum += nums[i];
if (curSum > sum) {
curSum = nums[i];
++cnt;
if (cnt > m) return false;
}
}
return true;
}
};
``````

``````class Solution {
public:
int splitArray(vector<int>& nums, int m) {
int n = nums.size();
vector<long> sums(n + 1);
vector<vector<long>> dp(m + 1, vector<long>(n + 1, LONG_MAX));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
sums[i] = sums[i - 1] + nums[i - 1];
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = i - 1; k < j; ++k) {
long val = max(dp[i - 1][k], sums[j] - sums[k]);
dp[i][j] = min(dp[i][j], val);
}
}
}
return dp[m][n];
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/410

Reverse Pairs

https://leetcode.com/problems/split-array-largest-sum/

https://leetcode.com/problems/split-array-largest-sum/discuss/89816/DP-Java

https://leetcode.com/problems/split-array-largest-sum/discuss/89873/binary-search-c-solution

https://leetcode.com/problems/split-array-largest-sum/discuss/89817/Clear-Explanation%3A-8ms-Binary-Search-Java

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation