Keshawn_lu's Blog

Leetcode 410. 分割数组的最大值

字数统计: 597阅读时长: 2 min
2020/07/25 Share

题目简介:

给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)

示例:

1
2
3
4
5
6
7
8
9
10
11
输入:
nums = [7,2,5,10,8]
m = 2

输出:
18

解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8],
因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。

思路:

动态规划,dp[i][j]代表前i个数字分成j段,所有情况下,其各段和的最大值中的最小值。

首先定义一个sub[i],代表前i个数字的和。

对于dp[i][j],我们可以定义一个k,将i个数分成1 ~ kk + 1 ~ i,其中1 ~ k包括了前j - 1段,则第j段的数字便为k + 1 ~ i

所以每次划分,得到的和的最大值long sum = max(dp[k][j - 1], sub[i] - sub[k]),即j - 1段的和的最大值的最小值与第j段的和进行比较。

最后dp[i][j]为这些最大值的最小值,即min(dp[i][j], sum)

最后返回dp[nums.size()][m]即可。

tips:

  • 由于i个数字最多只能分成i段,所以j <= min(i, m)。(即m > nums.size()时返回0即可)。
  • 需要使用long来存储数组,否则会溢出。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
int splitArray(vector<int>& nums, int m) {

//dp[i][j], 前i个数分成j段后的 和的最大值的 最小值
vector<vector<long>> dp(nums.size() + 1, vector<long>(m + 1, INT_MAX));
//sub[i], 前i个数的和
vector<long> sub(nums.size() + 1, 0);

sub[1] = nums[0];
for(int i = 2; i <= nums.size(); i++){

sub[i] = sub[i - 1] + nums[i - 1];
}

dp[0][0] = 0;
for(int i = 1; i <= nums.size(); i++){

for(int j = 1; j <= min(i, m); j++){

//前k个数分成了j - 1段, k + 1 ~ i 为第j段
for(int k = 0; k < i; k++){

//第j - 1段的 和的最大值的 最小值 与第j段的和进行比较, 得出最大值
long sum = max(dp[k][j - 1], sub[i] - sub[k]);
dp[i][j] = min(dp[i][j], sum);
}
}
}

return dp[nums.size()][m];
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: