Accepted Java simple solution (a little bit DP, but naive)


  • 0
    Q
    public class Solution {
        
        int m=0;
        int n=0;
        int[][] sums2;
        int[][] matrix;
        
        public int maxSumSubmatrix(int[][] matrix, int k) {
            this.matrix = matrix;
            
            if(matrix==null) return 0;
            m = matrix.length;
            if(m==0) return 0;
            n = matrix[0].length;
            if(n==0) return 0;
            
            /* sum2[i][j] = matrix[0][j] +...+ matrix[i][j],
             * sum2 represents sum of a vertical area whose width is 1.
             */
            sums2 = new int[n][m];
            
            for(int j=0;j<n;j++) {
                for(int i=0;i<m;i++) {
                    sums2[j][i] = (i==0 ? 0 : sums2[j][i-1]) + matrix[i][j];
                }
            }
            
            int res = Integer.MIN_VALUE;
            
            for(int i=0;i<m;i++) {
                for(int j=0;j<n;j++) {
                    for(int height=1;height<=m && i+height<=m;height++) {
                        int[] dp = new int[n+1];
                        for(int width=1;width<=n && j+width<=n;width++) {
                            dp[width] = dp[width-1] + getCol(i, j+width-1, height);
                            if(dp[width] == k) return k;
                            if(dp[width] < k && dp[width]>res) {
                                res = dp[width];
                            }
                        }
                    }
                }
            }
            return res;
        }
        
        public int getCol(int i, int j, int height) {
            if(height==1) {
                return matrix[i][j];
            } else {
                if(i==0) {
                    return sums2[j][i+height-1];
                } else {
                    return sums2[j][i+height-1] - sums2[j][i-1];
                }
            }
        }
    }
    

Log in to reply
 

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