ผลรวมสี่เหลี่ยมที่ใหญ่ที่สุดที่เล็กกว่า num ใน JavaScript

ปัญหา

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ 2 มิติของ Numbers เป็นอาร์กิวเมนต์แรก และหมายเลขผลรวมเป้าหมายเป็นอาร์กิวเมนต์ที่สอง

ฟังก์ชันของเราควรหาสี่เหลี่ยมนั้นจากอาร์เรย์ 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