Getting the submatrix with maximum sum?

Question

With the help of the Algorithmist and Larry and a modification of Kadane's Algorithm, here is my solution:

int dim = matrix.length;
    //computing the vertical prefix sum for columns
    int[][] ps = new int[dim][dim];
    for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
            if (j == 0) {
                ps[j][i] = matrix[j][i];
            } else {
                ps[j][i] = matrix[j][i] + ps[j - 1][i];
            }
        }
    }
    int maxSoFar = 0;
    int min , subMatrix;
    //iterate over the possible combinations applying Kadane's Alg.
    //int toplefti =0, topleftj=0, bottomrighti=0, bottomrightj=0;
    for (int i = 0; i < dim; i++) {
        for (int j = i; j < dim; j++) {
            min = 0;
            subMatrix = 0;
            for (int k = 0; k < dim; k++) {
                if (i == 0) {
                    subMatrix += ps[j][k];
                } else {
                    subMatrix += ps[j][k] - ps[i-1][k];
                }
                if(subMatrix < min){                        
                    min = subMatrix;
                }
                if((subMatrix - min) > maxSoFar){
                    maxSoFar = subMatrix - min;
                }                    
            }
        }
    }

The only problem left is to determine the submatrix elements, i mean the top left and the bottom right corners. I managed to do this in one dimensional case. Any suggestions?

Answer 1

Have a look at JAMA package; I believe it will make your life easier.

Answer 2

This is a Dynamic Programming problem, and you can read about the O(N^3) solution at Algorithmist.

Answer 3

With the help of the Algorithmist and Larry and a modification of Kadane's Algorithm, here is my solution:

int dim = matrix.length;
    //computing the vertical prefix sum for columns
    int[][] ps = new int[dim][dim];
    for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
            if (j == 0) {
                ps[j][i] = matrix[j][i];
            } else {
                ps[j][i] = matrix[j][i] + ps[j - 1][i];
            }
        }
    }
    int maxSoFar = 0;
    int min , subMatrix;
    //iterate over the possible combinations applying Kadane's Alg.
    for (int i = 0; i < dim; i++) {
        for (int j = i; j < dim; j++) {
            min = 0;
            subMatrix = 0;
            for (int k = 0; k < dim; k++) {
                if (i == 0) {
                    subMatrix += ps[j][k];
                } else {
                    subMatrix += ps[j][k] - ps[i - 1 ][k];
                }
                if(subMatrix < min){
                    min = subMatrix;
                }
                if((subMatrix - min) > maxSoFar){
                    maxSoFar = subMatrix - min;
                }                    
            }
        }
    }

The only thing left is to determine the submatrix elements, i.e: the top left and the bottom right corner of the submatrix. Anyone suggestion?