জাভাস্ক্রিপ্টে সংখ্যার চেয়ে ছোট আয়তক্ষেত্রের যোগফল

সমস্যা

আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা প্রথম আর্গুমেন্ট হিসাবে 2-ডি অ্যারে সংখ্যা এবং দ্বিতীয় আর্গুমেন্ট হিসাবে একটি টার্গেট যোগ সংখ্যা নেয়৷

আমাদের ফাংশনটি 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