Print maximum sum square sub-matrix of given size

Last Updated : 14 Oct, 2023

Given an N x N matrix, find a k x k submatrix where k <= N and k >= 1, such that sum of all the elements in submatrix is maximum. The input matrix can contain zero, positive and negative numbers.

For example consider below matrix, if k = 3, then output should print the sub-matrix enclosed in blue.

rectangle

We strongly recommend you to minimize your browser and try this yourself first.

A Simple Solution is to consider all possible sub-squares of size k x k in our input matrix and find the one which has maximum sum. Time complexity of above solution is O(N²k²).
We can solve this problem in O(N²) time. This problem is mainly an extension of this problem of printing all sums. The idea is to preprocess the given square matrix. In the preprocessing step, calculate sum of all vertical strips of size k x 1 in a temporary square matrix stripSum[][]. Once we have sum of all vertical strips, we can calculate sum of first sub-square in a row as sum of first k strips in that row, and for remaining sub-squares, we can calculate sum in O(1) time by removing the leftmost strip of previous subsquare and adding the rightmost strip of new square.

Below is the implementation of above idea.

C++

// An efficient C++ program to find maximum sum sub-square
// matrix
#include <bits/stdc++.h>
using namespace std;
 
// Size of given matrix
#define N 5
 
// A O(n^2) function to the maximum sum sub-squares of size
// k x k in a given square matrix of size n x n
void printMaxSumSub(int mat[][N], int k)
{
    // k must be smaller than or equal to n
    if (k > N)
        return;
 
    // 1: PREPROCESSING
    // To store sums of all strips of size k x 1
    int stripSum[N][N];
 
    // Go column by column
    for (int j = 0; j < N; j++) {
        // Calculate sum of first k x 1 rectangle in this
        // column
        int sum = 0;
        for (int i = 0; i < k; i++)
            sum += mat[i][j];
        stripSum[0][j] = sum;
 
        // Calculate sum of remaining rectangles
        for (int i = 1; i < N - k + 1; i++) {
            sum += (mat[i + k - 1][j] - mat[i - 1][j]);
            stripSum[i][j] = sum;
        }
    }
 
    // max_sum stores maximum sum and its position in matrix
    int max_sum = INT_MIN, *pos = NULL;
 
    // 2: CALCULATE SUM of Sub-Squares using stripSum[][]
    for (int i = 0; i < N - k + 1; i++) {
        // Calculate and print sum of first subsquare in
        // this row
        int sum = 0;
        for (int j = 0; j < k; j++)
            sum += stripSum[i][j];
 
        // Update max_sum and position of result
        if (sum > max_sum) {
            max_sum = sum;
            pos = &(mat[i][0]);
        }
 
        // Calculate sum of remaining squares in current row
        // by removing the leftmost strip of previous
        // sub-square and adding a new strip
        for (int j = 1; j < N - k + 1; j++) {
            sum += (stripSum[i][j + k - 1]
                    - stripSum[i][j - 1]);
 
            // Update max_sum and position of result
            if (sum > max_sum) {
                max_sum = sum;
                pos = &(mat[i][j]);
            }
        }
    }
 
    // Print the result matrix
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++)
            cout << *(pos + i * N + j) << " ";
        cout << endl;
    }
}
 
// Driver program to test above function
int main()
{
    int mat[N][N] = {
        { 1, 1, 1, 1, 1 }, { 2, 2, 2, 2, 2 },
        { 3, 8, 6, 7, 3 }, { 4, 4, 4, 4, 4 },
        { 5, 5, 5, 5, 5 },
    };
    int k = 3;
 
    cout << "Maximum sum 3 x 3 matrix is\n";
    printMaxSumSub(mat, k);
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

C

// An efficient C program to find maximum sum sub-square
// matrix
#include <limits.h>
#include <stdio.h>
 
// Size of given matrix
#define N 5
 
// A O(n^2) function to the maximum sum sub-squares of size
// k x k in a given square matrix of size n x n
void printMaxSumSub(int mat[][N], int k)
{
    // k must be smaller than or equal to n
    if (k > N)
        return;
 
    // 1: PREPROCESSING
    // To store sums of all strips of size k x 1
    int stripSum[N][N];
 
    // Go column by column
    for (int j = 0; j < N; j++) {
        // Calculate sum of first k x 1 rectangle in this
        // column
        int sum = 0;
        for (int i = 0; i < k; i++)
            sum += mat[i][j];
        stripSum[0][j] = sum;
 
        // Calculate sum of remaining rectangles
        for (int i = 1; i < N - k + 1; i++) {
            sum += (mat[i + k - 1][j] - mat[i - 1][j]);
            stripSum[i][j] = sum;
        }
    }
 
    // max_sum stores maximum sum and its position in matrix
    int max_sum = INT_MIN, *pos = NULL;
 
    // 2: CALCULATE SUM of Sub-Squares using stripSum[][]
    for (int i = 0; i < N - k + 1; i++) {
        // Calculate and print sum of first subsquare in
        // this row
        int sum = 0;
        for (int j = 0; j < k; j++)
            sum += stripSum[i][j];
 
        // Update max_sum and position of result
        if (sum > max_sum) {
            max_sum = sum;
            pos = &(mat[i][0]);
        }
 
        // Calculate sum of remaining squares in current row
        // by removing the leftmost strip of previous
        // sub-square and adding a new strip
        for (int j = 1; j < N - k + 1; j++) {
            sum += (stripSum[i][j + k - 1]
                    - stripSum[i][j - 1]);
 
            // Update max_sum and position of result
            if (sum > max_sum) {
                max_sum = sum;
                pos = &(mat[i][j]);
            }
        }
    }
 
    // Print the result matrix
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++)
            printf("%d ", *(pos + i * N + j));
        printf("\n");
    }
}
 
// Driver program to test above function
int main()
{
    int mat[N][N] = {
        { 1, 1, 1, 1, 1 }, { 2, 2, 2, 2, 2 },
        { 3, 8, 6, 7, 3 }, { 4, 4, 4, 4, 4 },
        { 5, 5, 5, 5, 5 },
    };
    int k = 3;
 
    printf("Maximum sum 3 x 3 matrix is\n");
    printMaxSumSub(mat, k);
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// An efficient Java program to find maximum sum
// sub-square matrix
 
// Class to store the position of start of
// maximum sum in matrix
class Position {
    int x;
    int y;
 
    // Constructor
    Position(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
 
    // Updates the position if new maximum sum
    // is found
    void updatePosition(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
 
    // returns the current value of X
    int getXPosition() { return this.x; }
 
    // returns the current value of y
    int getYPosition() { return this.y; }
}
 
class Gfg {
    // Size of given matrix
    static int N;
 
    // A O(n^2) function to the maximum sum sub-
    // squares of size k x k in a given square
    // matrix of size n x n
    static void printMaxSumSub(int[][] mat, int k)
    {
 
        // k must be smaller than or equal to n
        if (k > N)
            return;
 
        // 1: PREPROCESSING
        // To store sums of all strips of size k x 1
        int[][] stripSum = new int[N][N];
 
        // Go column by column
        for (int j = 0; j < N; j++) {
 
            // Calculate sum of first k x 1 rectangle
            // in this column
            int sum = 0;
            for (int i = 0; i < k; i++)
                sum += mat[i][j];
            stripSum[0][j] = sum;
 
            // Calculate sum of remaining rectangles
            for (int i = 1; i < N - k + 1; i++) {
                sum += (mat[i + k - 1][j] - mat[i - 1][j]);
                stripSum[i][j] = sum;
            }
        }
 
        // max_sum stores maximum sum and its
        // position in matrix
        int max_sum = Integer.MIN_VALUE;
        Position pos = new Position(-1, -1);
 
        // 2: CALCULATE SUM of Sub-Squares using
        // stripSum[][]
        for (int i = 0; i < N - k + 1; i++) {
 
            // Calculate and print sum of first subsquare
            // in this row
            int sum = 0;
            for (int j = 0; j < k; j++)
                sum += stripSum[i][j];
 
            // Update max_sum and position of result
            if (sum > max_sum) {
                max_sum = sum;
                pos.updatePosition(i, 0);
            }
 
            // Calculate sum of remaining squares in
            // current row by removing the leftmost
            // strip of previous sub-square and adding
            // a new strip
            for (int j = 1; j < N - k + 1; j++) {
                sum += (stripSum[i][j + k - 1] - stripSum[i][j - 1]);
 
                // Update max_sum and position of result
                if (sum > max_sum) {
                    max_sum = sum;
                    pos.updatePosition(i, j);
                }
            }
        }
 
        // Print the result matrix
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++)
                System.out.print(mat[i + pos.getXPosition()][j + pos.getYPosition()]
                                 + " ");
            System.out.println();
        }
    }
 
    // Driver program to test above function
    public static void main(String[] args)
    {
        N = 5;
        int[][] mat = { { 1, 1, 1, 1, 1 },
                        { 2, 2, 2, 2, 2 },
                        { 3, 8, 6, 7, 3 },
                        { 4, 4, 4, 4, 4 },
                        { 5, 5, 5, 5, 5 } };
        int k = 3;
 
        System.out.println("Maximum sum 3 x 3 matrix is");
        printMaxSumSub(mat, k);
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Python3

# An efficient Python3 program to find maximum sum
# sub-square matrix
 
# Size of given matrix
N = 5
 
# A O(n^2) function to the maximum sum sub-
# squares of size k x k in a given square
# matrix of size n x n
def printMaxSumSub(mat, k):
 
    # k must be smaller than or equal to n
    if (k > N):
        return;
 
    # 1: PREPROCESSING
    # To store sums of all strips of size k x 1
    stripSum = [[0 for j in range(N)] for i in range(N)];
 
    # Go column by column
    for j in range(N):
         
        # Calculate sum of first k x 1 rectangle
        # in this column
        sum = 0;
        for i in range(k):
            sum += mat[i][j];
        stripSum[0][j] = sum;
 
        # Calculate sum of remaining rectangles
        for i in range(1,N-k+1):
            sum += (mat[i+k-1][j] - mat[i-1][j]);
            stripSum[i][j] = sum;
 
    # max_sum stores maximum sum and its
    # position in matrix
    max_sum = -1000000000
    i_ind = 0
    j_ind = 0
 
    # 2: CALCULATE SUM of Sub-Squares using stripSum[][]
    for i in range(N-k+1):
         
        # Calculate and print sum of first subsquare
        # in this row
        sum = 0;
        for j in range(k):
            sum += stripSum[i][j];
 
        # Update max_sum and position of result
        if (sum > max_sum):
            max_sum = sum;
            i_ind = i
            j_ind = 0
 
 
        # Calculate sum of remaining squares in
        # current row by removing the leftmost
        # strip of previous sub-square and adding
        # a new strip
        for j in range(1,N-k+1):
            sum += (stripSum[i][j+k-1] - stripSum[i][j-1]);
 
            # Update max_sum and position of result
            if (sum > max_sum):
                max_sum = sum;
                i_ind = i
                j_ind = j
 
    # Print the result matrix
    for i in range(k):
        for j in range(k):
            print(mat[i+i_ind][j+j_ind], end = ' ')
        print()
 
# Driver program to test above function
mat = [[1, 1, 1, 1, 1],
        [2, 2, 2, 2, 2],
        [3, 8, 6, 7, 3],
        [4, 4, 4, 4, 4],
        [5, 5, 5, 5, 5],
    ];
k = 3;
print("Maximum sum 3 x 3 matrix is");
printMaxSumSub(mat, k);
 
# This code is contributed by rutvik_56.

C#

// An efficient C# program to find maximum sum 
// sub-square matrix 
using System;
 
// Class to store the position of start of 
// maximum sum in matrix 
class Position 
{ 
    int x; 
    int y; 
 
    // Constructor 
    public Position(int x, int y)
    { 
        this.x = x; 
        this.y = y; 
    } 
 
    // Updates the position if new maximum sum 
    // is found 
    public void updatePosition(int x, int y)
    { 
        this.x = x; 
        this.y = y; 
    } 
 
    // returns the current value of X 
    public int getXPosition()
    { 
        return this.x; 
    } 
 
    // returns the current value of y 
    public int getYPosition() 
    { 
        return this.y; 
    } 
} 
 
class GFG 
{ 
     
    // Size of given matrix 
    static int N; 
 
    // A O(n^2) function to the maximum sum sub- 
    // squares of size k x k in a given square 
    // matrix of size n x n 
    static void printMaxSumSub(int[,] mat, int k) 
    { 
 
        // k must be smaller than or equal to n 
        if (k > N) 
            return; 
 
        // 1: PREPROCESSING 
        // To store sums of all strips of size k x 1 
        int[,] stripSum = new int[N, N]; 
 
        // Go column by column 
        for (int j = 0; j < N; j++) 
        { 
 
            // Calculate sum of first k x 1 rectangle 
            // in this column 
            int sum = 0; 
            for (int i = 0; i < k; i++) 
                sum += mat[i, j]; 
            stripSum[0, j] = sum; 
 
            // Calculate sum of remaining rectangles 
            for (int i = 1; i < N - k + 1; i++) 
            { 
                sum += (mat[i + k - 1, j] - 
                        mat[i - 1, j]); 
                stripSum[i, j] = sum; 
            } 
        } 
 
        // max_sum stores maximum sum and its 
        // position in matrix 
        int max_sum = int.MinValue; 
        Position pos = new Position(-1, -1); 
 
        // 2: CALCULATE SUM of Sub-Squares using stripSum[,] 
        for (int i = 0; i < N - k + 1; i++)
        { 
 
            // Calculate and print sum of first subsquare 
            // in this row 
            int sum = 0; 
            for (int j = 0; j < k; j++) 
                sum += stripSum[i, j]; 
 
            // Update max_sum and position of result 
            if (sum > max_sum) 
            { 
                max_sum = sum; 
                pos.updatePosition(i, 0); 
            } 
 
            // Calculate sum of remaining squares in 
            // current row by removing the leftmost 
            // strip of previous sub-square and adding 
            // a new strip 
            for (int j = 1; j < N - k + 1; j++) 
            { 
                sum += (stripSum[i, j + k - 1] - 
                        stripSum[i, j - 1]); 
 
                // Update max_sum and position of result 
                if (sum > max_sum)
                { 
                    max_sum = sum; 
                    pos.updatePosition(i, j); 
                } 
            } 
        } 
 
        // Print the result matrix 
        for (int i = 0; i < k; i++) 
        { 
            for (int j = 0; j < k; j++) 
            { 
                Console.Write(mat[i + pos.getXPosition(),
                                  j + pos.getYPosition()] + " "); 
            } 
            Console.WriteLine(); 
        } 
    } 
 
    // Driver Code
    public static void Main(String[] args) 
    { 
        N = 5; 
        int[,] mat = {{ 1, 1, 1, 1, 1 }, 
                      { 2, 2, 2, 2, 2 }, 
                        { 3, 8, 6, 7, 3 }, 
                      { 4, 4, 4, 4, 4 }, 
                      { 5, 5, 5, 5, 5 }}; 
        int k = 3; 
 
        Console.WriteLine("Maximum sum 3 x 3 matrix is"); 
        printMaxSumSub(mat, k); 
    } 
} 
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// An efficient Javascript program to find maximum sum 
// sub-square matrix 
 
// Class to store the position of start of 
// maximum sum in matrix 
class Position 
{ 
    constructor()
    {
        this.x = 0;
        this.y = 0;
    }
 
    // Constructor 
    Position(x, y)
    { 
        this.x = x; 
        this.y = y; 
    } 
 
    // Updates the position if new maximum sum 
    // is found 
    updatePosition(x, y)
    { 
        this.x = x; 
        this.y = y; 
    } 
 
    // returns the current value of X 
    getXPosition()
    { 
        return this.x; 
    } 
 
    // returns the current value of y 
    getYPosition() 
    { 
        return this.y; 
    } 
} 
 
// Size of given matrix 
var N = 0; 
// A O(n^2) function to the maximum sum sub- 
// squares of size k x k in a given square 
// matrix of size n x n 
function printMaxSumSub(mat, k) 
{ 
    // k must be smaller than or equal to n 
    if (k > N) 
        return; 
    // 1: PREPROCESSING 
    // To store sums of all strips of size k x 1 
    var stripSum = Array.from(Array(N), ()=>Array(N));
    // Go column by column 
    for (var j = 0; j < N; j++) 
    { 
        // Calculate sum of first k x 1 rectangle 
        // in this column 
        var sum = 0; 
        for (var i = 0; i < k; i++) 
            sum += mat[i][j]; 
        stripSum[0][j] = sum; 
        // Calculate sum of remaining rectangles 
        for (var i = 1; i < N - k + 1; i++) 
        { 
            sum += (mat[i + k - 1][j] - 
                    mat[i - 1][j]); 
            stripSum[i][j] = sum; 
        } 
    } 
    // max_sum stores maximum sum and its 
    // position in matrix 
    var max_sum = -1000000000; 
    var pos = new Position(-1, -1); 
    // 2: CALCULATE SUM of Sub-Squares using stripSum[,] 
    for (var i = 0; i < N - k + 1; i++)
    { 
        // Calculate and print sum of first subsquare 
        // in this row 
        var sum = 0; 
        for (var j = 0; j < k; j++) 
            sum += stripSum[i][j]; 
        // Update max_sum and position of result 
        if (sum > max_sum) 
        { 
            max_sum = sum; 
            pos.updatePosition(i, 0); 
        } 
        // Calculate sum of remaining squares in 
        // current row by removing the leftmost 
        // strip of previous sub-square and adding 
        // a new strip 
        for (var j = 1; j < N - k + 1; j++) 
        { 
            sum += (stripSum[i][j + k - 1] - 
                    stripSum[i][j - 1]); 
            // Update max_sum and position of result 
            if (sum > max_sum)
            { 
                max_sum = sum; 
                pos.updatePosition(i, j); 
            } 
        } 
    } 
    // Print the result matrix 
    for (var i = 0; i < k; i++) 
    { 
        for (var j = 0; j < k; j++) 
        { 
            document.write(mat[i + pos.getXPosition()][
                              j + pos.getYPosition()] + " "); 
        } 
        document.write("<br>"); 
    } 
} 
// Driver Code
N = 5; 
var mat = [[ 1, 1, 1, 1, 1 ], 
              [ 2, 2, 2, 2, 2 ], 
                [ 3, 8, 6, 7, 3 ], 
              [ 4, 4, 4, 4, 4 ], 
              [ 5, 5, 5, 5, 5 ]]; 
var k = 3; 
document.write("Maximum sum 3 x 3 matrix is<br>"); 
printMaxSumSub(mat, k); 
 
 
 
</script>

Output

Maximum sum 3 x 3 matrix is
8 6 7 
4 4 4 
5 5 5

Time complexity: O(N²).
Auxiliary Space: O(N²).

Approach#2: Using dynamic programming

The approach used in this code is based on dynamic programming. A 2D dp table is initialized and populated with the cumulative sum of the elements in the matrix. Then, for each possible submatrix of size size, the sum is calculated by subtracting the sum of the elements outside the submatrix. The maximum sum and the corresponding submatrix are kept track of throughout the process. Finally, the submatrix with the maximum sum is returned.

Algorithm

1. Create a 2D DP array of the same size as the input matrix and initialize it with the corresponding elements of the input matrix.
2. Compute the sum of elements in each submatrix of size size x size using the DP array.
3. Find the maximum sum submatrix using the computed sums and return it.

C++

#include <iostream>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the submatrix with maximum sum
vector<vector<int>> max_sum_submatrix(vector<vector<int>>& matrix, int size) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    vector<vector<int>> dp(rows, vector<int>(cols, 0));
 
    // Calculate cumulative sum matrix
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            dp[i][j] = matrix[i][j];
            if (i > 0) dp[i][j] += dp[i - 1][j]; // Add sum from top
            if (j > 0) dp[i][j] += dp[i][j - 1]; // Add sum from left
            if (i > 0 && j > 0) dp[i][j] -= dp[i - 1][j - 1]; // Remove overlapping
        }
    }
 
    int max_sum = INT_MIN;
    vector<vector<int>> max_submatrix;
 
    // Iterate through possible submatrices
    for (int i = size - 1; i < rows; i++) {
        for (int j = size - 1; j < cols; j++) {
            int submatrix_sum = dp[i][j];
            if (i >= size) submatrix_sum -= dp[i - size][j]; // Subtract sum from top
            if (j >= size) submatrix_sum -= dp[i][j - size]; // Subtract sum from left
            if (i >= size && j >= size) submatrix_sum += dp[i - size][j - size]; // Add overlapping
 
            // Update maximum submatrix sum
            if (submatrix_sum > max_sum) {
                max_sum = submatrix_sum;
                max_submatrix.clear();
                for (int r = i - size + 1; r <= i; r++) {
                    vector<int> row;
                    for (int c = j - size + 1; c <= j; c++) {
                        row.push_back(matrix[r]); // Construct the submatrix
                    }
                    max_submatrix.push_back(row);
                }
            }
        }
    }
 
    return max_submatrix;
}
 
int main() {
    vector<vector<int>> matrix = {{1, 1, 1, 1, 1},
                                  {2, 2, 2, 2, 2},
                                  {3, 8, 6, 7, 3},
                                  {4, 4, 4, 4, 4},
                                  {5, 5, 5, 5, 5}};
    int size = 3;
    vector<vector<int>> max_submatrix = max_sum_submatrix(matrix, size);
 
    cout << "Maximum sum " << size << " x " << size << " matrix is" << endl;
    for (const vector<int>& row : max_submatrix) {
        for (int x : row) {
            cout << x << " ";
        }
        cout << endl;
    }
 
    return 0;
}
// This code is contributed by shivamgupta310570

Java

import java.util.ArrayList;
import java.util.List;
 
public class MaxSumSubmatrix {
    // Function to find the submatrix with maximum sum
    public static List<List<Integer>> maxSumSubmatrix(int[][] matrix, int size) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
 
        // Calculate cumulative sum matrix
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dp[i][j] = matrix[i][j];
                if (i > 0) dp[i][j] += dp[i - 1][j]; // Add sum from top
                if (j > 0) dp[i][j] += dp[i][j - 1]; // Add sum from left
                if (i > 0 && j > 0) dp[i][j] -= dp[i - 1][j - 1]; // Remove overlapping
            }
        }
 
        int maxSum = Integer.MIN_VALUE;
        List<List<Integer>> maxSubmatrix = new ArrayList<>();
 
        // Iterate through possible submatrices
        for (int i = size - 1; i < rows; i++) {
            for (int j = size - 1; j < cols; j++) {
                int submatrixSum = dp[i][j];
                if (i >= size) submatrixSum -= dp[i - size][j]; // Subtract sum from top
                if (j >= size) submatrixSum -= dp[i][j - size]; // Subtract sum from left
                if (i >= size && j >= size) submatrixSum += dp[i - size][j - size]; // Add overlapping
 
                // Update maximum submatrix sum
                if (submatrixSum > maxSum) {
                    maxSum = submatrixSum;
                    maxSubmatrix.clear();
                    for (int r = i - size + 1; r <= i; r++) {
                        List<Integer> row = new ArrayList<>();
                        for (int c = j - size + 1; c <= j; c++) {
                            row.add(matrix[r]); // Construct the submatrix
                        }
                        maxSubmatrix.add(row);
                    }
                }
            }
        }
 
        return maxSubmatrix;
    }
 
    public static void main(String[] args) {
        int[][] matrix = {
            {1, 1, 1, 1, 1},
            {2, 2, 2, 2, 2},
            {3, 8, 6, 7, 3},
            {4, 4, 4, 4, 4},
            {5, 5, 5, 5, 5}
        };
        int size = 3;
        List<List<Integer>> maxSubmatrix = maxSumSubmatrix(matrix, size);
 
        System.out.println("Maximum sum " + size + " x " + size + " matrix is");
        for (List<Integer> row : maxSubmatrix) {
            for (int x : row) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
    }
}

Python3

def max_sum_submatrix(matrix, size):
    rows = len(matrix)
    cols = len(matrix[0])
    dp = [[0] * cols for _ in range(rows)]
    for i in range(rows):
        for j in range(cols):
            dp[i][j] = matrix[i][j]
            if i > 0:
                dp[i][j] += dp[i-1][j]
            if j > 0:
                dp[i][j] += dp[i][j-1]
            if i > 0 and j > 0:
                dp[i][j] -= dp[i-1][j-1]
    max_sum = float('-inf')
    for i in range(size-1, rows):
        for j in range(size-1, cols):
            submatrix_sum = dp[i][j]
            if i >= size:
                submatrix_sum -= dp[i-size][j]
            if j >= size:
                submatrix_sum -= dp[i][j-size]
            if i >= size and j >= size:
                submatrix_sum += dp[i-size][j-size]
            if submatrix_sum > max_sum:
                max_sum = submatrix_sum
                max_submatrix = [row[j-size+1:j+1] for row in matrix[i-size+1:i+1]]
    return max_submatrix
 
matrix = [[1, 1, 1, 1, 1],
          [2, 2, 2, 2, 2],
          [3, 8, 6, 7, 3],
          [4, 4, 4, 4, 4],
          [5, 5, 5, 5, 5]]
size = 3
max_submatrix = max_sum_submatrix(matrix, size)
print("Maximum sum {} x {} matrix is".format(size, size))
for row in max_submatrix:
    print(" ".join(str(x) for x in row))

C#

using System;
using System.Collections.Generic;
 
class Program
{
    static List<List<int>> MaxSumSubmatrix(List<List<int>> matrix, int size)
    {
        int rows = matrix.Count;
        int cols = matrix[0].Count;
        List<List<int>> dp = new List<List<int>>();
 
        // Initialize dp with zeros
        for (int i = 0; i < rows; i++)
        {
            dp.Add(new List<int>());
            for (int j = 0; j < cols; j++)
            {
                dp[i].Add(0);
            }
        }
 
        // Calculate cumulative sum matrix
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                dp[i][j] = matrix[i][j];
                if (i > 0) dp[i][j] += dp[i - 1][j]; // Add sum from top
                if (j > 0) dp[i][j] += dp[i][j - 1]; // Add sum from left
                if (i > 0 && j > 0) dp[i][j] -= dp[i - 1][j - 1]; // Remove overlapping
            }
        }
 
        int maxSum = int.MinValue;
        List<List<int>> maxSubmatrix = new List<List<int>>();
 
        // Iterate through possible submatrices
        for (int i = size - 1; i < rows; i++)
        {
            for (int j = size - 1; j < cols; j++)
            {
                int submatrixSum = dp[i][j];
                if (i >= size) submatrixSum -= dp[i - size][j]; // Subtract sum from top
                if (j >= size) submatrixSum -= dp[i][j - size]; // Subtract sum from left
                if (i >= size && j >= size) submatrixSum += dp[i - size][j - size]; // Add overlapping
 
                // Update maximum submatrix sum
                if (submatrixSum > maxSum)
                {
                    maxSum = submatrixSum;
                    maxSubmatrix.Clear();
                    for (int r = i - size + 1; r <= i; r++)
                    {
                        List<int> row = new List<int>();
                        for (int c = j - size + 1; c <= j; c++)
                        {
                            row.Add(matrix[r]); // Construct the submatrix
                        }
                        maxSubmatrix.Add(row);
                    }
                }
            }
        }
 
        return maxSubmatrix;
    }
 
    static void Main(string[] args)
    {
        List<List<int>> matrix = new List<List<int>>
        {
            new List<int> {1, 1, 1, 1, 1},
            new List<int> {2, 2, 2, 2, 2},
            new List<int> {3, 8, 6, 7, 3},
            new List<int> {4, 4, 4, 4, 4},
            new List<int> {5, 5, 5, 5, 5}
        };
 
        int size = 3;
        List<List<int>> maxSubmatrix = MaxSumSubmatrix(matrix, size);
 
        Console.WriteLine("Maximum sum " + size + " x " + size + " matrix is:");
        foreach (List<int> row in maxSubmatrix)
        {
            foreach (int x in row)
            {
                Console.Write(x + " ");
            }
            Console.WriteLine();
        }
    }
}

Javascript

// JavaScript Program for the above approach
function max_sum_submatrix(matrix, size) {
    const rows = matrix.length;
    const cols = matrix[0].length;
    const dp = new Array(rows).fill(0).map(() => new Array(cols).fill(0));
 
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            dp[i][j] = matrix[i][j];
            if (i > 0) dp[i][j] += dp[i - 1][j];
            if (j > 0) dp[i][j] += dp[i][j - 1];
            if (i > 0 && j > 0) dp[i][j] -= dp[i - 1][j - 1];
        }
    }
 
    let max_sum = Number.MIN_SAFE_INTEGER;
    let max_submatrix = [];
 
    for (let i = size - 1; i < rows; i++) {
        for (let j = size - 1; j < cols; j++) {
            let submatrix_sum = dp[i][j];
            if (i >= size) submatrix_sum -= dp[i - size][j];
            if (j >= size) submatrix_sum -= dp[i][j - size];
            if (i >= size && j >= size) submatrix_sum += dp[i - size][j - size];
 
            if (submatrix_sum > max_sum) {
                max_sum = submatrix_sum;
                max_submatrix = matrix.slice(i - size + 1, i + 1).map(row => row.slice(j - size + 1, j + 1));
            }
        }
    }
 
    return max_submatrix;
}
 
const matrix = [
    [1, 1, 1, 1, 1],
    [2, 2, 2, 2, 2],
    [3, 8, 6, 7, 3],
    [4, 4, 4, 4, 4],
    [5, 5, 5, 5, 5]
];
const size = 3;
const max_submatrix = max_sum_submatrix(matrix, size);
 
console.log(`Maximum sum ${size} x ${size} matrix is:`);
max_submatrix.forEach(row => console.log(row.join(" ")));
// THIS CODE IS CONTRIBUTED BY PIYUSH AGARWAL

Output

Maximum sum 3 x 3 matrix is
8 6 7
4 4 4
5 5 5

Time complexity: O(rows * cols).
Space complexity: O(rows * cols).

Suggest improvement

Shortest path in a Binary Maze

Validity of a given Tic-Tac-Toe board configuration

Share your thoughts in the comments

Basic Operations on Matrix

Easy problems on Matrix

Intermediate problems on Matrix

Hard problems on Matrix

Basic Operations on Matrix

Easy problems on Matrix

Intermediate problems on Matrix

Hard problems on Matrix

Print maximum sum square sub-matrix of given size

C++

C

Java

Python3

C#

Javascript

Approach#2: Using dynamic programming

Algorithm

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?