JavaScript 中小于 num 的最大矩形和
问题
我们需要编写一个JavaScript函数，它接受一个二维数组作为第一个参数，一个目标和数作为第二个参数。
我们的函数应该从二维数组中找出在数组中所有矩形中总和最大但小于或等于函数的第二个参数指定的目标总和的矩形。
然后该函数应该最终返回最大的总和。例如，如果函数的输入是-
const arr = [ [1, 0, 1], [0, -2, 3] ]; const num = 2;
那么输出应该是-
const output = 2;
输出说明：
因为最小的矩形是-
[ [0, 1] [-2, 3] ]
示例
此代码将是-
const arr = [
[1, 0, 1],
[0, -2, 3]
];
const num = 2;
const maxSum = (arr = [], num = 1) => {
const rows = arr.length;
const cols = arr[0].length;
let maxSum = -Infinity;
for(let l = 0; l < rows; l++) {
const dp = Array(cols).fill(0);
for(let r = l; r < rows; r++) {
let sum = 0, max = -Infinity;
for(let c = 0; c < cols; c++) {
dp[c] += arr[r][c];
if(sum < 0) sum = 0;
sum += dp[c];
max = Math.max(max, sum);
}
if(max <= num) maxSum = Math.max(max, maxSum);
else {
max = -Infinity;
for(let c = 0; c < cols; c++) {
sum = 0;
for(let d = c; d < cols; d++) {
sum += dp[d];
if(sum <= num) max = Math.max(sum, max);
}
}
maxSum = Math.max(max, maxSum);
}
if(maxSum === num) return num;
}
}
return maxSum;
};
console.log(maxSum(arr, num));输出结果控制台中的输出将是-
2
热门推荐
10 幼教专干调动祝福语简短
11 少先队代表送祝福语简短
12 中秋祝福语送朋友简短
13 20岁简短生日祝福语
14 孙女结婚姥姥祝福语简短
15 美女蛋糕祝福语简短英文
16 青春告白祖国简短祝福语
17 祝福语签名简短大全女生
18 近代生日祝福语简短精辟