数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究JavaScript 中小于 num 的最大矩形和
问题
我们要求编写一个 JavaScript 函数，该函数将一个数字的 2-D 数组作为第一个参数和一个目标和数作为第二个参数。
我们的函数应找出 2-D 数组中所有矩形中和最大的矩形，但仅小于或等于函数传递的第二个参数的目标和。
最后，函数应返回最大和。例如，如果传递给函数的输入为 −
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
更新时间： 18-Mar-2021
100 次浏览
广告