Answers for "find all submatrix of a matrix"

find submatrix in matrix

class Main
{
    // Find the maximum sum submatrix present in a given matrix
    public static int findMaxSumSubmatrix(int matrix[][])
    {
        // `M × N` matrix
        final int M = matrix.length;
        final int N = matrix[0].length;
 
        // `S[i][j]` stores the sum of submatrix formed by row 0 to `i-1`
        // and column 0 to `j-1`
        int[][] S = new int[M+1][N+1];
 
        // preprocess the matrix to fill `S`
        for (int i = 0; i <= M; i++)
        {
            for (int j = 0; j <= N; j++)
            {
                if (i == 0 || j == 0) {
                    S[i][j] = 0;
                }
                else {
                    S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] +
                                    matrix[i-1][j-1];
                }
            }
        }
 
        int maxSum = Integer.MIN_VALUE;
        int rowStart = 0, rowEnd = 0, colStart = 0, colEnd = 0;
 
        // consider every submatrix formed by row `i` to `j`
        // and column `m` to `n`
        for (int i = 0; i < M; i++)
        {
            for (int j = i; j < M; j++)
            {
                for (int m = 0; m < N; m++)
                {
                    for (int n = m; n < N; n++)
                    {
                        // calculate the submatrix sum using `S[][]` in `O(1)` time
                        int submatrix_sum = S[j+1][n+1] - S[j+1][m]
                                            - S[i][n+1] + S[i][m];
 
                        // if the submatrix sum is more than the maximum found so far
                        if (submatrix_sum > maxSum)
                        {
                            maxSum = submatrix_sum;
                            rowStart = i;
                            rowEnd = j;
                            colStart = m;
                            colEnd = n;
                        }
                    }
                }
            }
        }
 
        System.out.println("The submatrix is formed by rows "
                            + rowStart + " to " + rowEnd +
                            " and columns from "
                            + colStart + " to " + colEnd);
 
        return maxSum;
    }
 
    public static void main(String[] args)
    {
        // input matrix
        int matrix[][] =
        {
            { -5, -6, 3, 1, 0 },
            { 9, 7, 8, 3, 7 },
            { -6, -2, -1, 2, -4 },
            { -7, 5, 5, 2, -6 },
            { 3, 2, 9, -5, 1 }
        };
 
        // find the maximum sum submatrix
        System.out.print("The maximum sum of the submatrix is " +
                                findMaxSumSubmatrix(matrix));
    }
}