資料結構
網路
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 次瀏覽
廣告