B站视频源
原题
给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
注意:
数组长度 n 满足以下条件:
1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
示例:
输入: nums = [7,2,5,10,8] m = 2 输出: 18 解释: 一共有四种方法将nums分割为2个子数组。 其中最好的方式是将其分为[7,2,5] 和 [10,8], 因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。
思路 – 动态规划
dp[i][j] 代表前 i 个元素,分成 j 组的情况下,全局最优值为 dp[i][j]
代码
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
// 重叠子问题 最优子结构
// dp[i][j] 将其前 i 个元素分成 j 组,全局最小值
// 7 2 5 10 8
// i dp[i][1] = sum[i]
// k i 从 1 到 k 分成 j - 1,从 k + 1到 i 分成一组
// dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sum[i] - sum[k]));
int n = nums.size();
long long dp[n + 5][55], sum[n + 5];
memset(dp, 0x3f, sizeof dp);
memset(sum, 0, sizeof sum);
for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + nums[i - 1];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= min(i, m); ++j) {
if (j == 1) {
dp[i][j] = sum[i];
} else {
for (int k = 1; k <= i - 1; ++k) {
dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sum[i] - sum[k]));
}
}
}
}
return dp[n][m];
}
};
复杂度分析
时间复杂度:O(n^2 * m) n 为数组长度,m 为分组个数
空间复杂度:O(n^2)
思路 – 二分搜索
找到目标值(全局最小值)的二段性,在目标值范围内进行二分搜索。
代码
class Solution {
public:
bool check(vector<int>& nums, int m, int target) {
long long cnt = 1, sum = 0 ;
for (int i = 0; i < nums.size(); ++i) {
if (sum + nums[i] > target) {
sum = nums[i];
++cnt;
} else {
sum += nums[i];
}
}
return cnt <= m;
}
int splitArray(vector<int>& nums, int m) {
// m = 2
// value: 7 2 5 10 8
// index: 1 2 3 4 5
// min: 10, max: 32
// 10, 11, 12, 13, ..... 17, 18, 19, 20, ..... 32
// -----不可行--------------,---------可行--------
long long l = 0, r = 0, mid;
for (auto n : nums) {
if (l < n) l = n;
r += n;
}
while (l < r) {
int mid = l + (r - l) / 2;
if (check(nums, m, mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};
复杂度分析
时间复杂度:O(n * logk) n 为数组的长度,k 为 10^{12}
空间复杂度:O(1)
参考
[1]. LeetCode 原题. https://leetcode-cn.com/problems/split-array-largest-sum/
欢迎分享,引用。若转载,请联系我,谢谢配合。 本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-410-split-array-largest-sum/