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

Mô tả vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một mảng 2D các số làm đối số đầu tiên và một số mục tiêu tổng làm đối số thứ hai.

Hàm phải tìm hình chữ nhật trong mảng 2D có tổng lớn nhất trong số tất cả các hình chữ nhật nhưng vừa đủ nhỏ hơn hoặc bằng tổng mục tiêu. Hàm trả về tổng lớn nhất đó.

Ví dụ, nếu đầu vào là:

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

Thì đầu ra nên 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ụ minh họa

Mã thực hiện:

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

Kết quả trong console sẽ là:

2