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

1. [7], [2,5,10,8]
2. [7,2], [5,8,10]
3. [7,2,5], [8,10]
4. [7,2,5,8], [10]

## 思路一：动态规划

```    public int splitArray(int[] nums, int m) {
//计算[0...i]中所有元素的和
int[] sums = new int[nums.length+1];
for(int i = 1 ; i<=nums.length ; i++) {
sums[i] = nums[i-1] + sums[i-1];
}
return splitArray(nums, m, 0, sums);
}

//计算从cur位置开始，将其分割为m个子数组的最小分割场景
public int splitArray(int[] nums, int m, int cur, int[] sums) {
if(m == 1) {
return sums[nums.length] - sums[cur];
}
int min = Integer.MAX_VALUE;
int diff = Integer.MAX_VALUE;
for(int i = cur+1 ; i<=nums.length-m+1 ; i++) {
//当前元素为止，左边的子数组的元素和
int left = sums[i]-sums[cur];
//对右边的剩余元素递归的调用splitArray方法
int right = splitArray(nums, m-1, i, sums);
//如果出现二者之间的差递增的情况，则说明距离最优分割越来越远，则停止继续尝试
if(diff < Math.abs(left - right)) {
break;
}
diff = Math.abs(left - right);
min = Math.min(min, Math.max(left, right));
}
return min;
}```

```    public int splitArray(int[] nums, int m)
{
int L = nums.length;
//记录0-i的元素和
int[] S = new int[L+1];
S[0]=0;
for(int i=0; i<L; i++)
S[i+1] = S[i]+nums[i];

//如果m=1，则最小分割结果对应的是整个数组中所有元素的和
int[] dp = new int[L];
for(int i=0; i<L; i++)
dp[i] = S[L]-S[i];

for(int s=1; s<m; s++)
{
for(int i=0; i<L-s; i++)
{
dp[i]=Integer.MAX_VALUE;
for(int j=i+1; j<=L-s; j++)
{
int t = Math.max(dp[j], S[j]-S[i]);
if(t<=dp[i])
dp[i]=t;
else
break;
}
}
}

return dp[0];
}```

## 思路二：二分法

```    public int splitArray2(int[] nums, int m) {
long sum = 0;
int max = Integer.MIN_VALUE;
for(int i = 0 ; i<nums.length ; i++) {
max = Math.max(max, nums[i]);
sum += nums[i];
}
if(m == 1) {
return (int)sum;
}
long lft = max;
long rgt = sum;
while(lft <= rgt) {
long mid = (lft + rgt) / 2;
if(valid(nums, m, mid)) {
rgt = mid - 1;
}else {
lft = mid + 1;
}
}
return (int) lft;

}

public boolean valid(int[] nums, int m, long target) {
int count = 1;
long sum = 0;
for(int i = 0 ; i<nums.length ; i++) {
sum += nums[i];
if(sum > target) {
sum = nums[i];
count++;
if(count > m) {
return false;
}
}
}
return true;
}```

0 条评论

• ### leetcode330. Patching Array

假设有一个有序的正整数数组nums和一个整数n，最少添加几个元素到这个数组中，使得从1-n的所有整数都可以由这个数组中的值的或是几个值的和构成。

• ### leetcode525. Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equa...

• ### leetcode363. Max Sum of Rectangle No Larger Than K

现有一个由整数构成的矩阵，问从中找到一个子矩阵，要求该子矩阵中各个元素的和为不超过k的最大值，问子矩阵中元素的和为多少? 注：后面的文章中将使用[左上角顶点坐标...

• ### LeetCode第一题

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

• ### 让priority_queue支持小根堆的几种方法

点击这里了解什么是priority_queue 前言 priority_queue默认是大根堆，也就是大的元素会放在前面 例如 ? #include<io...

• ### Dimple在左耳听风ARTS打卡（第九期）

所谓ARTS： 每周至少做一个LeetCode的算法题；阅读并点评至少一篇英文技术文章；学习至少一个技术技巧；分享一篇有观点和思考的技术文章。（也就是Algor...

• ### LeetCode题组：第26题-删除排序数组中的重复项

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。（注意这里提到了排序数组，也就是说数组是有序的。如果无序，...

• ### 第88场周赛

第二反应：根据上述这个模拟超时过程，想一优化，shifts数组后面开始，逐个偏移，根据描述，后面的偏移会加到前面。于是有了后缀和这一说法。

• ### 十大经典排序算法整理汇总（附代码）

本文整理并总结了十大经典的排序算法（冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、计数排序、基数排序、桶排序、堆排序）的时间复杂度、空间复杂度等性...