JavaScript 中最大的子数组总和
问题
我们需要编写一个JavaScript函数，它接受一个非负整数数组arr作为第一个参数，一个整数num(num 我们函数的任务是将数组拆分为num个非空的连续子数组。应该以这样的方式拆分数组，以最小化这些num个子数组中的最大总和。然后我们的函数应该返回子数组中累积的最大和。 例如，如果函数的输入是-const arr = [5, 1, 4, 8, 7];
const num = 2;
那么输出应该是-
const output = 15;
输出说明
虽然有四种方法可以将原始数组拆分为子数组，但是如果我们将数组拆分为两组[5,1,4]和[8,7]，那么这两组将具有最小的和，并且这两组中较大的是8+7=15我们的函数应该返回。
示例
此代码将是-
const arr = [5, 1, 4, 8, 7];
const num = 2;
const splitArray = (arr = [], num = 1) => {
let max = 0;
let sum = 0;
const split = (arr, mid) => {
let part = 1;
let tempSum = 0;
for (let num of arr) {
if (tempSum + num > mid) {
tempSum = num;
part++;
} else {
tempSum += num;
}
}
return part;
};
for (let num of arr) {
max = Math.max(max, num);
sum += num;
};
let low = max;
let high = sum;
while (low < high) {
let mid = Math.floor((high+low)/2);
let part = split(arr, mid);
if (part > num) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
};
console.log(splitArray(arr, num));代码说明：
我们在这里使用二分搜索来检查我们是否可以找到最佳分割。
输出结果
控制台中的输出将是-
15