2D मैट्रिक्स में अधिकतम योग आयत

एक मैट्रिक्स दिया गया है। हमें एक आयत (कभी-कभी वर्ग) मैट्रिक्स खोजने की जरूरत है, जिसका योग अधिकतम हो।

इस एल्गोरिथ्म के पीछे का विचार बाएँ और दाएँ स्तंभों को ठीक करना है और प्रत्येक पंक्ति के लिए बाएँ स्तंभ से दाएँ स्तंभ तक के तत्व का योग ज्ञात करने का प्रयास करना है, और इसे अस्थायी रूप से संग्रहीत करना है। हम ऊपर और नीचे की पंक्ति संख्याएँ खोजने का प्रयास करेंगे। अस्थायी सरणी प्राप्त करने के बाद, हम अधिकतम योग उप-सरणी प्राप्त करने के लिए कडाने के एल्गोरिदम को लागू कर सकते हैं। इससे कुल आयत बन जाएगा।

इनपुट और आउटपुट

Input:
The matrix of integers.
 1  2 -1 -4 -20
-8 -3  4  2   1
 3  8  10 1   3
-4 -1   1 7  -6

Output:
The top left point and bottom right point of the submatrix, and the total sum of the submatrix.
(Top, Left) (1, 1)
(Bottom, Right) (3, 3)
The max sum is: 29

एल्गोरिदम

kadaneAlgorithm(सरणी, प्रारंभ, अंत, n)

इनपुट: सरणी में योग, प्रारंभ और समाप्ति बिंदु, तत्वों की संख्या होगी।

आउटपुट - आरंभ और समाप्ति बिंदु खोजें।

Begin
   sum := 0 and maxSum := - ∞
   end := -1
   tempStart := 0

   for each element i in the array, do
      sum := sum + array[i]
      if sum < 0, then
         sum := 0
         tempStart := i + 1
      else if sum > maxSum, then
         maxSum := sum
         start := tempStart
         end := i
   done

   if end ≠ -1, then
      return maxSum
   maxSum := array[0], start := 0 and end := 0

   for each element i from 1 to n of array, do
      if array[i] > maxSum, then
         maxSum := array[i]
         start := i and end := i
   done

   return maxSum
End

मैक्ससमरेक्ट (मैट्रिक्स)

इनपुट: दिया गया मैट्रिक्स।

आउटपुट: आयत का अधिकतम योग।

Begin
   maxSum := - ∞
   define temp array, whose size is same as row of matrix

   for left := 0 to number of columns in the Matrix, do
      till temp array with 0s
      for right := left to column of matrix -1, do
         for each row i, do
            temp[i] := matrix[i, right]
         done

         sum := kadaneAlgorithm(temp, start, end, number of rows)
            if sum > maxSum, then
               maxSum := sum
               endLeft := left
               endRight := right
               endTop := start
               endBottom := end
      done
   done

   display top left and bottom right corner and the maxSum
End

उदाहरण

#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) {    //find max sum and starting and ending location
   int sum = 0, maxSum = INT_MIN;

   end = -1;    //at first no place is selected

   int tempStart = 0;    //starting from 0

   for (int i = 0; i < n; i++) {
      sum += arr[i];
      if (sum < 0) {
         sum = 0;
         tempStart = i+1;
      }else if (sum > maxSum) {     //get maximum sum, and update start and end index
         maxSum = sum;
         start = tempStart;
         end = i;
      }
   }

   if (end != -1)
      return maxSum;
   //when all elements are negative in the array
   maxSum = arr[0];
   start = end = 0;

   // Find the maximum element in array
   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<ROW; i++)//temp initially holds all 0
         temp[i] = 0;

      for (right = left; right < COL; ++right) {
         for (int i = 0; i < ROW; ++i)    //for each row, find the sum
            temp[i] += M[i][right];
         sum = kadaneAlgo(temp, start, end, ROW);    //find sum of rectangle (top, left) and (bottom right)

         if (sum > maxSum) {    //find maximum value of sum, then update corner points
            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