Python栈的应用：矩阵中最大子矩阵的面积

题目描述

给定一个 N 行 M 列的正整数矩阵，求其中最大的子矩阵的面积。

输入格式

第一行包含两个整数 N 和 M。

接下来 N 行，每行包含 M 个正整数，表示矩阵中的元素。

输出格式

输出一个整数，表示最大的子矩阵的面积。

数据范围

1≤N≤200
1≤M≤200
1≤矩阵中元素≤1000

输入样例

4 5
2 3 4 5 1
1 2 3 4 5
3 2 1 2 3
4 3 2 1 2

输出样例

12

算法1

(暴力枚举) $O(n^6)$

最简单的实现方法是，枚举每个矩阵左上角和右下角的位置，然后计算这个矩阵内所有数的和，并更新答案即可。

时间复杂度

矩阵个数是 O(n^4)，计算每个矩阵内所有数的和时间复杂度是 O(n^2),所以总时间复杂度是 O(n^6)。

Python 代码