C प्रोग्राम में दिए गए आकार का अधिकतम योग वाला वर्ग उप-मैट्रिक्स प्रिंट करें

समस्या विवरण

N x N का एक मैट्रिक्स दिया गया है, M x M का एक उप-मैट्रिक्स ढूंढें जहां M <= N और M >= 1 ताकि मैट्रिक्स M x M के सभी तत्वों का योग अधिकतम हो। मैट्रिक्स N x N के इनपुट में शून्य, सकारात्मक और नकारात्मक पूर्णांक मान हो सकते हैं।

उदाहरण

इनपुट: 
{{1, 1, 1, 1, 1},
 {2, 2, 2, 2, 2},
 {3, 3, 3, 3, 3},
 {4, 4, 4, 4, 4},
 {5, 5, 5, 5, 5}}
आउटपुट:
4 4
5 5

एल्गोरिदम

शुरुआत
चरण 1: void matrix(int arr[][size], int k) फंक्शन घोषित करें
    यदि k > size तो वापस करें
    int array[size][size] घोषित करें
    j = 0 से size-1 तक लूप
        sum = 0 सेट करें
        i = 0 से k-1 तक लूप
            sum = sum + arr[i][j]
        अंत
        array[0][j] = sum सेट करें
        i = 1 से size-k तक लूप
            sum = sum + (arr[i+k-1][j] - arr[i-1][j])
            array[i][j] = sum सेट करें
        अंत
    अंत
    int maxsum = INT_MIN और *pos = NULL सेट करें
    i = 0 से size-k तक लूप
        int sum = 0 सेट करें
        j = 0 से k-1 तक लूप
            sum += array[i][j]
        अंत
        यदि sum > maxsum तो
            maxsum = sum सेट करें
            pos = &(arr[i][0]) सेट करें
        अंत
        j = 1 से size-k तक लूप
            sum += (array[i][j+k-1] - array[i][j-1])
            यदि sum > maxsum तो
                maxsum = sum सेट करें
                pos = &(arr[i][j]) सेट करें
            अंत
        अंत
    अंत
    i = 0 से k-1 तक लूप
        j = 0 से k-1 तक लूप
            *(pos + i*size + j) प्रिंट करें
        अंत
        \n प्रिंट करें
    अंत
चरण 2: main() में
    int array[size][size] = {{1,1,1,1,1}, {2,2,2,2,2}, {3,3,3,3,3}, {4,4,4,4,4}, {5,5,5,5,5}} घोषित करें
    int k = 2 घोषित करें
    matrix(array, k) कॉल करें
रोकें

C++ प्रोग्राम उदाहरण

#include <bits/stdc++.h>
using namespace std;
#define size 5

void matrix(int arr[][size], int k){
    if (k > size) return;
    int array[size][size];
    for (int j = 0; j < size; j++){
        int sum = 0;
        for (int i = 0; i < k; i++)
            sum += arr[i][j];
        array[0][j] = sum;
        for (int i = 1; i < size-k+1; i++){
            sum += (arr[i+k-1][j] - arr[i-1][j]);
            array[i][j] = sum;
        }
    }
    int maxsum = INT_MIN, *pos = NULL;
    for (int i = 0; i < size-k+1; i++){
        int sum = 0;
        for (int j = 0; j < k; j++)
            sum += array[i][j];
        if (sum > maxsum){
            maxsum = sum;
            pos = &(arr[i][0]);
        }
        for (int j = 1; j < size-k+1; j++){
            sum += (array[i][j+k-1] - array[i][j-1]);
            if (sum > maxsum){
                maxsum = sum;
                pos = &(arr[i][j]);
            }
        }
    }
    for (int i = 0; i < k; i++){
        for (int j = 0; j < k; j++)
            cout << *(pos + i*size + j) << " ";
        cout << endl;
    }
}

int main(){
    int array[size][size] = {
        {1, 1, 1, 1, 1},
        {2, 2, 2, 2, 2},
        {3, 3, 3, 3, 3},
        {4, 4, 4, 4, 4},
        {5, 5, 5, 5, 5},
    };
    int k = 2;
    matrix(array, k);
    return 0;
}

आउटपुट

उपरोक्त प्रोग्राम चलाने पर निम्नलिखित आउटपुट उत्पन्न होगा:

4 4
5 5