Given a 2D matrix, find the submatrix which sum of all elements is max


  • -3
    A

    public int subMaxMatrix(int[][] matrix) {

    	int[][] total = matrix;
    	for (int i = 1; i < matrix[0].length; i++) {
    		for (int j = 0; j < matrix.length; j++) {
    			total[i][j] += total[i-1][j];
    		}
    	}
    	
    	int maximum = Integer.MIN_VALUE;
    	for (int i = 0; i < matrix.length; i++) {
                for (int j = i; j < matrix.length; j++) {
                int[] result = new int[matrix[0].length];
    			for (int f = 0; f < matrix[0].length; f++) {
    				if (i == 0) {
    					result[f] = total[j][f];
    				} else {
    					result[f] = total[j][f] - total[i - 1][f];
    				}
    			}
    			int maximal = maxSubsequence(result);
    			
    			if (maximal > maximum) {
    				maximum = maximal;
    			}
    		}
    	}	
    	return maximum;
    

    }


  • 0
    D

    Could you please share your algorithm?


  • 0
    R
    b[][]=0
    for j 0->n-1:
    	int sum=0;
    	for i 0->m-1;
    		b[i+1][j]+=b[i][j];
    int maxsum=INT_MIN;
    for i 0->m-1:
    	int sum=0;
    	for j i->m-1:
    		dp = 0
    		for k in 0->n-1:
    			sum+=b[j+1][k]-b[i][k]
    			dp=max(dp+sum, sum);
    			maxsum=max(maxsum, dp);
    return maxsum;

  • 0
    A

    is there's a O(N^2) solution?


  • 1
    H

    Here is my runnable code:

    This is the result class to store the desired sub matrix:

    public class result {
        public int row, col, col_size, row_size;
    }
    

    Here is the rest of the code:

    public class questions {
    
    public static void main(String[] args) {
    
        int [][] matrix = new int[][]{
                {2, 2, 8},
                {1, 3, -9}
        };
    
        result res = new result();
        System.out.println("max sum = " + subMatrixSum(matrix, res));
        System.out.print("row = " + res.row + " col = " + res.col + " row size =" + res.row_size + " col size = " + res.col_size);
    
    
    }
    
    public static int subMatrixSum(int[][] matrix, result res) {
        int maxSum = -Integer.MAX_VALUE;
    
        for (int i = 1; i <= matrix.length; i++)
            for (int j = 1; j <= matrix[0].length; j++)
                for (int iIndex = 0; iIndex < matrix.length - i + 1; iIndex++)
                    for (int jIndex = 0; jIndex < matrix[0].length - j + 1; jIndex++) {
                        int sum = 0;
    
                        for (int k_i = iIndex; k_i < iIndex + i; k_i++)
                            for (int k_j = jIndex; k_j < jIndex + j; k_j++)
                                sum += matrix[k_i][k_j];
    
                        if (maxSum < sum) {
                            maxSum = sum;
                            res.row = iIndex;
                            res.col = jIndex;
                            res.row_size = i;
                            res.col_size = j;
                        }
                    }
        return maxSum;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.