GitHub Account Google Scholar Account LinkedIn Account Twitter Account flickr Account vialab Research Group Profile Page

Finding the Maximum Submatrix Within Another Matrix

Date: May 23, 2016
This algorithm works by employing Kadane's algorithm on an array whose values represent the sum of the rows of a submatrix.

Time Complexity: O(n2 * m)
Space Complexity: O(m)
Where n is the number of columns and m is the number of rows
public class MaximumSubmatrix {

    public static void main(String[] args) {

        int[][] matrix = new int[][]{{1, -5, -5},
                                    {1, 3, -4},
                                    {1, 3, 5},
                                    {-9, 6, 5}};

        findMaxSubmatrix(matrix);
    }

    public static void findMaxSubmatrix(int[][] matrix) {

        int rowLength = matrix.length;
        int colLength = matrix[0].length;
        int maxSum = matrix[0][0];
        int maxRowStart = 0;
        int maxRowEnd = 0;
        int maxColStart = 0;
        int maxColEnd = 0;

        for (int startCol = 0; startCol < colLength; startCol++) {

            int[] rowSum = new int[rowLength];

            for (int endCol = startCol; endCol < colLength; endCol++) {

                // Add up the column values for each row
                for (int row = 0; row < rowLength; row++) {

                    rowSum[row] += matrix[row][endCol];
                }

                /////////////////////////////////
                // Find the maximum subarray in
                // rowSum using Kadane's algorithm
                /////////////////////////////////
                int tempMax = rowSum[0];
                int tempRowStart = 0;
                int tempRowEnd = 0;

                int curSum = rowSum[0];
                int curStart = 0;
                int curEnd = 0;

                for (int i = 1; i < rowLength; i++) {

                    if (rowSum[i] > curSum + rowSum[i]) {

                        curStart = i;
                        curEnd = i;
                        curSum = rowSum[i];

                    } else {
                        curEnd = i;
                        curSum += rowSum[i];

                    }

                    if (curSum > tempMax) {

                        tempRowStart = curStart;
                        tempRowEnd = curEnd;
                        tempMax = curSum;
                    }
                }
                /////////////////////////////////

                if (tempMax > maxSum) {
                    maxSum = tempMax;
                    maxColStart = startCol;
                    maxColEnd = endCol;
                    maxRowStart = tempRowStart;
                    maxRowEnd = tempRowEnd;
                }
            }
        }

        System.out.println(
            "The maximum submatrix has a sum of " + maxSum
            + " and starts at row " + maxRowStart
            + " and colum " + maxColStart + " and ends at"
            + " row " + maxRowEnd + " and column "
            + maxColEnd);
    }
}