题目描述 ：给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。
    题目数据保证总会存在一个数值和不超过 k 的矩形区域。
    image.png
    示例1：

    输入：matrix = [[1,0,1],[0,-2,3]], k = 2输出：2 解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

    思考 ： DP、前缀和、状态压缩
    1、朴素二维前缀和（暴力）

    • 时间复杂度为：O(N4)。
    • 空间复杂度：O(N2)。

    代码：

    1. class Solution {
    2.     public int maxSumSubmatrix(int[][] matrix, int k) {
    3.         int R = matrix.length;
    4.         int C = matrix[0].length;
    5.         int[][] dp = new int[R+1][C+1];
    6.         int maxSum = Integer.MIN_VALUE;
    7.         for(int i1 = 1; i1 <= R; i1++){
    8.             for(int j1 = 1; j1<= C; j1++){
    9.                 for(int[] OneDimension : dp){
    10.                     Arrays.fill(OneDimension, 0);
    11.                 }
    12.                 dp[i1][j1] = matrix[i1-1][j1-1];
    13.                 for(int i2 = i1; i2 <= R; i2++){
    14.                     for(int j2 = j1; j2<= C; j2++){
    15.                         dp[i2][j2] = dp[i2][j2-1] + dp[i2-1][j2] -
    16.                                     dp[i2-1][j2-1] + matrix[i2-1][j2-1];
    17.                         if(dp[i2][j2] <= k && dp[i2][j2] > maxSum){
    18.                             maxSum = dp[i2][j2];
    19.                         }
    20.                     }
    21.                 }
    22.             }
    23.         }
    24.         return maxSum;
    25.     }
    26. }

    2、思想还是定边界，先定行的上下边界，把时间复杂度定在O(N2)，然后再遍历左右边界，时间复杂度控制在O(M)，细节待补充。
    3、疑问：在加了 K 的约束后，一维上的前缀和算法不成立了，如何解决这个问题