การหาสี่เหลี่ยมผืนผ้าที่มีผลรวมมากที่สุดแต่ไม่เกินค่าเป้าหมายใน JavaScript

ปัญหา

หา rectangle ใน 2D array ที่มีผลรวมมากที่สุดแต่ <= target number

ตัวอย่าง

arr = [[1,0,1],[0,-2,3]], target = 2
output: 2 (rectangle [[0,1],[-2,3]] sum = 2)

ตัวอย่างโค้ด

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

คำอธิบาย

Fixed left row l, right row r บีบอัดคอลัมน์เป็น 1D array dp แล้วหา max subarray sum <= target

ใช้ Kadane's algorithm หา max subarray sum หากเกิน target ใช้ brute force O(cols²) หา max <= target

Time: O(rows² * cols²) worst case