超级经典的求二维子矩阵和最大问题

我又不会做

思路：

• 先看一维的最大子矩阵怎么求？
  • 采用dp的思想f[i]为第a[i]结尾的最大连续子矩阵的和，f[i] = max(0, f[i - 1) + a[i]. 很好理解，当第i - 1列最大子矩阵和为负数，我们肯定不会选它。
• 扩展到二维最大子矩阵的和
  • 我们先枚举矩形的上下界，当上下界固定的时候，我们就可以把这几行看成是同一行，在采用一维的方式即可，时间复杂度为$O(N^3)$