JavaScript 中小于 num 的最大矩形和

Z时代
2024-01-10
分类：综合

问题

我们需要编写一个 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));