Tổng hình chữ nhật lớn nhất nhỏ hơn num trong JavaScript

Vấn đề

Chúng tôi bắt buộc phải viết một hàm JavaScript lấy mảng Số 2-D làm đối số đầu tiên và số tổng mục tiêu làm đối số thứ hai.

Hàm của chúng ta sẽ tìm ra hình chữ nhật đó từ mảng 2-D có tổng lớn nhất trong số tất cả các hình chữ nhật trong mảng nhưng chỉ nhỏ hơn hoặc bằng tổng mục tiêu được chỉ định bởi đối số thứ hai cho hàm.

Sau đó, hàm cuối cùng sẽ trả về tổng lớn nhất đó. Ví dụ:nếu đầu vào của hàm là -

const arr = [
   [1, 0, 1],
   [0, -2, 3]
];
const num = 2;

Sau đó, đầu ra phải là -

const output = 2;

Giải thích đầu ra:

Vì hình chữ nhật nhỏ nhất là -

[
   [0, 1]
   [-2, 3]
]

Ví dụ

Mã cho điều này sẽ là -

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));

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

2