《最大子矩阵》题目分析

本题是一道经典的面试题目。

首先我们可以枚举矩阵的左边界和右边界，不妨设为L和R。这一步枚举的时间复杂度是O(N^2)。

一旦确定L和R，问题就2维降到了1维。我们令

B[0] = A[0][L] + A[0][L+1] + ... + A[0][R]
B[1] = A[1][L] + A[1][L+1] + ... + A[1][R]
....
B[N-1] = A[N-1][L] + B[N-1][L+1] + ... + B[N-1][R]

提示：经过O(N^2)的预处理前缀和之后，B数组的每一项可以O(1)求得。这里不再赘述。

原问题就转化为求B中最长的连续子数组，满足子数组的和不超过K。

注意到矩阵A中的元素都是正整数，所以B数组中的元素也都是正整数。于是我们就可以用双指针(也被称为滑动窗口)的方法解决B数组的问题：

初始时i=j=0

只要B[i] + ... + B[j]的和小于等于K就令j累加1;否则令i累加1。  

直到i==N。在此过程中，j-i的最大值就代表了最长的子数组。

当然实现的时候还有一些边界问题要处理，我们就不赘述了。