LeetCode 410 Split Array Largest Sum
题目分析
https://leetcode.com/problems/split-array-largest-sum/
注意是非空的连续子数组。
暴力遍历法 / 递归法 / 动态规划法
时间复杂度 O(mn)
class Solution {
public:
vector<vector<int>> cache;
int splitArray(vector<int>& nums, int m) {
vector<vector<int>> cache(m + 1, vector<int>(nums.size() + 1, -1));
this->cache = cache;
return helper(nums, m, 0);
}
int helper(vector<int>& nums, int m, int s) {
if (m == 1) {
int ans = 0;
for (int i = s; i < nums.size(); i++) {
ans += nums[i];
}
return ans;
}
if (cache[m][s] != -1) return cache[m][s];
int ans = INT_MAX;
int c = 0;
for (int i = s; m - 1 <= nums.size() - 1 - i; i++) {
c += nums[i];
ans = min(ans, max(c, helper(nums, m - 1, i + 1)));
}
cache[m][s] = ans;
return ans;
}
};
二分搜素
https://labuladong.gitee.io/algo/2/21/63/
这题似乎可以理解成leetcode 1011 的换皮，逻辑是一模一样的。 D天对应本题分割数组的数量m；按顺序装运对于本题的连续数组； 求最小运载能力即本题的求各数组和的最大值的最小值
题目让求的是将数组分为 m 个子数组时的最小最大子数组和， 反向思考，我们可以求最小的最大子数组和，其满足可以 m 分数组。
最后的代码与 LeetCode 1011 一模一样。
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
int l = *max_element(nums.begin(), nums.end());
int r = accumulate(nums.begin(), nums.end(), 0);
while (l <= r) {
int t = l + (r - l) / 2;
if (isOkay(nums, m, t)) {
r = t - 1;
} else {
l = t + 1;
}
}
return l;
}
bool isOkay(vector<int>& nums, int m, int x) {
int count = 1;
int rest = x;
for (int i = 0; i < nums.size(); i++) {
if (rest >= nums[i]) {
rest -= nums[i];
} else {
count++;
rest = x - nums[i];
}
}
return count <= m;
}
};