410. Split Array Largest Sum
解题思路——Dynamic Programming
- TC:
- SC:
本题要求我们将一个数组切割为 m 个非空子数组。考虑到切割为 m 个数组与需要参考切割为 m - 1 个数组的结果，所以可以使用动态规划来做，具体思考如下：
- 首先我们需要一个二维数组来保存切割数组前 i 个数为 j 个子数组的全局最小值，把它命名为
dp]i][j] - 接着我们思考一下，当 j 为 1 的时候的情况：
dp[i][1]表示将数组前 i 个数切割为一组的最小值，也就是数组前 i 个数的加总，我们记为sum[i] - 接下来我们考虑
j > 1的情况，这种情况我们可以简化一下：- 首先把划分为 j 个组看成，对于前 k 个数，划分为
j - 1个组，最后从k + 1到i划分为一组，对单个 k 计算出来的结果取最大值就是符合题目要求的一种可能性了。 - 我们可以对 k 做遍历之后，对所有计算出来的
dp[i][j]取最小值就是全局最优解了 - 动态规划公式：
- 首先把划分为 j 个组看成，对于前 k 个数，划分为
C++
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
int len = nums.size();
// sum[i]：记录前 i 个数的总和（下标从 1 开始）
vector<unsigned int> sum(len + 1, 0);
// dp[i][j]：记录前 i 个数倍分割为 j 个组的全局最小值（下标从 1 开始）
vector<vector<unsigned int>> dp(len + 1,
vector<unsigned int>(m + 1, UINT_MAX));
// 计算 sum 数组的值
for (int i = 1; i <= len; i++) sum[i] = sum[i - 1] + nums[i - 1];
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= min(i, m); j++) {
// 当 j 为 1（分割为一个组）时，数组 dp 的值跟所有元素总和一致
if (j == 1) {
dp[i][j] = sum[i];
} else {
// k 代表最后一个组划分的位置
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[len][m];
}
};
Javascript
var splitArray = function(nums, m) {
const len = nums.length;
// sum[i]：记录前 i 个数的总和（下标从 1 开始）
const sum = new Array(len +1).fill(0);
// dp[i][j]：记录前 i 个数倍分割为 j 个组的全局最小值（下标从 1 开始）
const dp = new Array(len + 1);
for(let i = 0;i < dp.length;i++) {
dp[i] = new Array(m + 1).fill(Number.MAX_SAFE_INTEGER);
}
// 计算 sum 数组的值
for (let i = 1; i <= len; i++) sum[i] = sum[i - 1] + nums[i - 1];
for (let i = 1; i <= len; i++) {
for (let j = 1; j <= Math.min(i, m); j++) {
// 当 j 为 1（分割为一个组）时，数组 dp 的值跟所有元素总和一致
if (j === 1) {
dp[i][j] = sum[i];
} else {
// k 代表最后一个组划分的位置
for (let k = 1; k <= i - 1; k++)
dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], sum[i] - sum[k]));
}
}
}
return dp[len][m];
};
解题思路——二分法
- TC:
，sum 表示数组元素加总， maxNum 表示数组最大的元素
- SC:
首先我们要先说明一下什么情况能用二分法求解：能用二分法求解的问题一定是连续且能被判断出边距的。
拿本题为例，本题要求的是所有子数组和的最大值的最小值。
接下来我们来探讨一下子数组和最大与最小的情况：
最大：当只有一个子数组的情况下，也就是
m = 1，且这个最大值为所有数组元素的加总最小：当数组的每个元素都是一个子数组时，也就是
m = nums.size()，且这个时候最小值为数组元素的最大值
综上所述，我们的答案将会落在 [数组元素的最大值, 所有数组元素的加总] 这个范围之间。
有了边距之后，我们需要一个方法来判断结果会落在哪一边，所以我们分别讨论一下当目标太大或太小会有什么结果：
- 目标太大：如果我们二分的落点比较大，那么数组必须拆分的子数组就比较少（
子数组数量 <= m），符合题意但需要继续缩小范围，所以我们会把右边界right移到二分落点mid上 - 目标太小：如果二分落点太小，数组必须拆分更多子数组，将导致
子数组数量 > m，不符合题意，所以需要将左边界left移到mid + 1
C++
class Solution {
public:
// 检查当前的 target 是否可以实现
bool isValid(vector<int>& nums, int m, unsigned int target) {
// group 记录为了满足当前的 target 需要拆分的子数组数量
int group = 1, sum = 0;
for (int i = 0; i < nums.size(); i++) {
// 如果当前数组遍历加总超过了 target，就表示需要再拆分出一个子数组出来
if (sum + nums[i] > target) {
sum = nums[i];
group++;
} else {
sum += nums[i];
}
}
return group <= m;
}
int splitArray(vector<int>& nums, int m) {
// 二分左边界应该是数组的最大值，右边界应该是数组所有元素的加总
unsigned int left = 0, right = 0, mid;
for (unsigned int num : nums) {
if (num > left) left = num;
right += num;
}
while (left < right) {
mid = (left + right) / 2;
if (isValid(nums, m, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};
Javascript
/**
* @param {number[]} nums
* @param {number} m
* @return {number}
*/
var splitArray = function(nums, m) {
// 二分左边界应该是数组的最大值，右边界应该是数组所有元素的加总
let left = 0, right = 0, mid;
for (let num of nums) {
if (num > left) left = num;
right += num;
}
while (left < right) {
mid = Math.floor((left + right) / 2);
if (isValid(nums, m, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
// 检查当前的 target 是否可以实现
function isValid(nums, m, target) {
// group 记录为了满足当前的 target 需要拆分的子数组数量
let group = 1, sum = 0;
for (let i = 0; i < nums.length; i++) {
// 如果当前数组遍历加总超过了 target，就表示需要再拆分出一个子数组出来
if (sum + nums[i] > target) {
sum = nums[i];
group++;
} else {
sum += nums[i];
}
}
return group <= m;
}