363. Max Sum of Rectangle No Larger Than K

Question

Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.

It is guaranteed that there will be a rectangle with a sum no larger than k.

Solution

前缀和，计算矩阵中每个位置对应的方形的和。
遍历方形的两个对角线上的点。
其面积等于大块加小块的面积减去两个长方形的面积。
如果面积有小于k的，则记录其最大值并返回。

Code

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int x = matrix.length, y = matrix[0].length, max = Integer.MIN_VALUE;
        int[][] sum = new int[x+1][y+1];
        
        for(int i = 1; i <= x; i++){
            int total = 0;
            for(int j = 1; j <= y; j++){
                total += matrix[i-1][j-1];
                sum[i][j] = sum[i-1][j] + total;
            }
        }
 
        for(int i = 0; i <= x; i++){
            for(int j = 0; j <= y; j++){
                for(int m = i + 1; m <= x; m++){
                    for(int n = j + 1; n <= y; n++){
                        int area = sum[m][n] + sum[i][j] - sum[m][j] - sum[i][n];
                        if(area <= k) max = Math.max(max, area);
                    }
                }
            }
        }
        return max;
    }
}