方法一：DP (TLE?)
brute force需要先枚举左上顶点 O(mn)，右下顶点 O(mn)，然后扫描面积 O(mn)，总时间复杂度 O((mn)^3)。
我们可以用DP优化。利用二维prefix sum，计算出所有(0,0)到(i,j)的面积。这样对于任意一个矩形，我们可以通过大矩形减去两块矩形加上被两次减去的矩形得到。
时间复杂度 O((mn)^2)
方法二：Prefix Sum + Binary Search
想办法把问题简化为一维的问题。
枚举任意两行，把两行内的元素“拍扁”，得到一个长度为n的数组。问题转化为找 sum<=k 的subarray。
用prefix sum的方法，subarray [i+1~j] 的sum可以表示为 prefixSum[j] - prefixSum[i]。
根据题意，我们要保证 prefixSum[j] - prefixSum[i] <= k，即 prefixSum[i] >= prefixSum[j] - k。
由此，我们可以遍历j，计算prefixSum，与此同时用二分去找到 prefixSum[i]，用prefixSum[j]-prefixSum[i]更新答案。
class Solution { public: int maxSumSubmatrix(vector<vector<int>>& matrix, int k) { int m=matrix.size(), n=m==0?0:matrix[0].size(); if (m==0 || n==0) return 0; int res=INT_MIN; for (int r1=0;r1<m;++r1){ vector<int> compress(n,0); for (int r2=r1;r2<m;++r2){ for (int j=0;j<n;++j) compress[j] += matrix[r2][j]; // find max subarray <=k in compress int curSum=0, maxSum=INT_MIN; set<int> prefixSum; prefixSum.insert(0); for (int x:compress){ curSum += x; auto it=prefixSum.lower_bound(curSum-k); if (it!=prefixSum.end()) maxSum=max(maxSum,curSum-*it); prefixSum.insert(curSum); } res = max(res,maxSum); } } return res; } };
时间复杂度 O(m^2 nlogn)，先处理row还是col会影响，选小的那个即可。
本题测试点比较恶心，上述代码枚举row，超时。用相同的方法枚举两列col，拍扁做能AC。
Reference
LeetCode 363. Max Sum of Rectangle No Larger Than K
原文：https://www.cnblogs.com/hankunyan/p/11269501.html