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

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

इस एल्गोरिदम के पीछे का विचार बाएं और दाएं कॉलम को फिक्स करना और प्रत्येक पंक्ति के लिए बाएं कॉलम से दाएं कॉलम तक के तत्वों का योग ढूंढना है, और उसे अस्थायी रूप से स्टोर करना है। हम ऊपर और नीचे की पंक्ति संख्या ढूंढने का प्रयास करेंगे। अस्थायी ऐरे प्राप्त करने के बाद, हम अधिकतम योग सब-ऐरे प्राप्त करने के लिए कडेन्स एल्गोरिदम लागू कर सकते हैं। इसके साथ, कुल आयत बनेगा।

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

इनपुट: पूर्णांकों का मैट्रिक्स
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
    ऐरे के प्रत्येक तत्व i के लिए 1 से n तक, करें
        यदि array[i] > maxSum, तो
            maxSum := array[i]
            start := i और end := i
    पूर्ण
    वापस maxSum
अंत

maxSumRect(Matrix)

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

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

शुरुआत
    maxSum := -∞
    temp ऐरे परिभाषित करें, जिसका आकार मैट्रिक्स की पंक्तियों जितना हो
    left := 0 से मैट्रिक्स में कॉलम की संख्या तक, करें
        temp ऐरे को 0 से भरें
        right := left से मैट्रिक्स के कॉलम -1 तक, करें
            प्रत्येक पंक्ति 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 < ROW; i++)
            temp[i] = 0;
        
        for (right = left; right < COL; ++right) {
            for (int i = 0; i < ROW; ++i)
                temp[i] += M[i][right];
            
            sum = kadaneAlgo(temp, start, end, ROW);
            if (sum > 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