JavaScript에서 num보다 작은 가장 큰 사각형 합계

문제

Numbers의 2차원 배열을 첫 번째 인수로, 목표 합계를 두 번째 인수로 취하는 JavaScript 함수를 작성해야 합니다.

우리의 함수는 배열의 모든 사각형 중에서 가장 큰 합을 갖지만 함수에 대한 두 번째 인수로 지정된 목표 합보다 작거나 같은 2차원 배열에서 해당 사각형을 찾아야 합니다.

그런 다음 함수는 최종적으로 가장 큰 합계를 반환해야 합니다. 예를 들어, 함수에 대한 입력이 -

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