২D ম্যাট্রিক্সে সর্বোচ্চ যোগফলযুক্ত আয়তক্ষেত্র

একটি ম্যাট্রিক্স দেওয়া আছে। আমাদের এমন একটি আয়তক্ষেত্র (কখনো কখনো বর্গাকার) ম্যাট্রিক্স খুঁজে বের করতে হবে যার উপাদানগুলোর যোগফল সর্বোচ্চ।

এই অ্যালগরিদমের মূল ধারণা হল বাম ও ডান কলাম ফিক্স করে রাখা এবং প্রতিটি সারির জন্য বাম কলাম থেকে ডান কলাম পর্যন্ত উপাদানগুলোর যোগফল বের করে অস্থায়ীভাবে সংরক্ষণ করা। তারপর উপরের ও নিচের সারির নম্বর খুঁজে বের করা। অস্থায়ী অ্যারে পাওয়ার পর ক্যাডেনের অ্যালগরিদম প্রয়োগ করে সর্বোচ্চ যোগফলযুক্ত সাবঅ্যারে বের করা যায়। এর মাধ্যমে পুরো আয়তক্ষেত্র গঠন হবে।

ইনপুট এবং আউটপুট

ইনপুট: পূর্ণসংখ্যার ম্যাট্রিক্স।
1   2  -1  -4 -20
-8 -3   4   2   1
3   8  10   1   3
-4  -1   1   7  -6

আউটপুট: সাবম্যাট্রিক্সের উপরের বাম এবং নিচের ডান বিন্দু, এবং মোট যোগফল।
(Top, Left) (1, 1)
(Bottom, Right) (3, 3)
The max sum is: 29

অ্যালগরিদম

kadaneAlgorithm(array, start, end, n)

ইনপুট: যোগফল ধারণকারী অ্যারে, শুরু ও শেষ বিন্দু, উপাদান সংখ্যা।
আউটপুট: শুরু এবং শেষ বিন্দু খুঁজে বের করা।

শুরু
  sum := 0 এবং maxSum := -∞
  end := -1
  tempStart := 0
  অ্যারেতে প্রতিটি উপাদান i জন্য, করুন
    sum := sum + array[i]
    যদি sum < 0 হয়, তবে
      sum := 0
      tempStart := i + 1
    অন্যথায় যদি sum > maxSum হয়, তবে
      maxSum := sum
      start := tempStart
      end := i
  শেষ
  যদি end ≠ -1 হয়, তবে
    ফেরত দিন maxSum
  maxSum := array[0], start := 0 এবং end := 0
  অ্যারেতে 1 থেকে n পর্যন্ত প্রতিটি উপাদান i জন্য, করুন
    যদি array[i] > maxSum হয়, তবে
      maxSum := array[i]
      start := i এবং end := i
  শেষ
  ফেরত দিন maxSum
শেষ

maxSumRect(Matrix)

ইনপুট: প্রদত্ত ম্যাট্রিক্স।
আউটপুট: আয়তক্ষেত্রের সর্বোচ্চ যোগফল।

শুরু
  maxSum := -∞
  temp অ্যারে সংজ্ঞায়িত করুন যেন এর আকার ম্যাট্রিক্সের সারির সমান
  left := 0 থেকে ম্যাট্রিক্সের কলাম সংখ্যা পর্যন্ত, করুন
    temp অ্যারে ০ দিয়ে পূরণ করুন
    right := left থেকে কলাম-১ পর্যন্ত, করুন
      প্রতিটি সারি i জন্য, করুন
        temp[i] := matrix[i, right]
      শেষ
      sum := kadaneAlgorithm(temp, start, end, সারির সংখ্যা)
      যদি sum > maxSum হয়, তবে
        maxSum := sum
        endLeft := left
        endRight := right
        endTop := start
        endBottom := end
    শেষ
  শেষ
  উপরের বাম এবং নিচের ডান কোণা এবং maxSum প্রদর্শন করুন
শেষ

উদাহরণ (C++)

#include <iostream>
#define ROW 4
#define COL 5
using namespace std;

int M[ROW][COL] = {
  {1, 2, -1, -4, -20},
  {-8, -3, 4, 2, 1},
  {3, 8, 10, 1, 3},
  {-4, -1, 1, 7, -6}
};

int kadaneAlgo(int arr[], int &start, int &end, int n) {
  int sum = 0, maxSum = INT_MIN;
  end = -1;
  int tempStart = 0;
  for (int i = 0; i < n; i++) {
    sum += arr[i];
    if (sum < 0) {
      sum = 0;
      tempStart = i+1;
    } else if (sum > maxSum) {
      maxSum = sum;
      start = tempStart;
      end = i;
    }
  }
  if (end != -1) return maxSum;
  maxSum = arr[0];
  start = end = 0;
  for (int i = 1; i < n; i++) {
    if (arr[i] > maxSum) {
      maxSum = arr[i];
      start = end = i;
    }
  }
  return maxSum;
}

void maxSumRect() {
  int maxSum = INT_MIN, endLeft, endRight, endTop, endBottom;
  int left, right;
  int temp[ROW], sum, start, end;
  for (left = 0; left < COL; left++) {
    for(int i = 0; i maxSum) {
        maxSum = sum;
        endLeft = left;
        endRight = right;
        endTop = start;
        endBottom = end;
      }
    }
  }
  cout << "(Top, Left) (" << endTop << ", " << endLeft << ")" << endl;
  cout << "(Bottom, Right) (" << endBottom << ", " << endRight << ")" << endl;
  cout << "The max sum is: " << maxSum;
}

int main() {
  maxSumRect();
}

আউটপুট

(Top, Left) (1, 1)
(Bottom, Right) (3, 3)
The max sum is: 29