#P871. 【TYVJ1466】最美妙的子矩阵

【TYVJ1466】最美妙的子矩阵

【问题描述】

candy的生日即将到来,飘飘乎居士希望找到一个最美妙的矩阵送个candy作为礼物,  飘飘乎居士从Pink处得知最美妙的矩阵满足三个条件:首先,它的长和宽都必须和矩阵的边界平行(也就是不可以出现斜的矩阵);第二:子矩阵横竖都要满足单调递增(可以相等,也就是对于每一个最优子矩阵的元素都要满足a[i][j]>=a[i-1][j] and a[i][j]>=a[i][j-1],其中a[i][j]表示矩阵第i行第j列的数字);第三:最优矩阵是在满足上述两个条件中面积最大的矩阵。

【输入格式】

第一行,两个正整数n,m

接下来n行,每行m个数字,构成一个n*m的矩阵

【输出格式】

一行,代表最优矩阵的面积

【输入样例】

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

【输出样例】

6

【样例说明】

最优子矩阵为

2 4 4
4 4 4

该矩阵满足横竖都单调递增,并且是所有满足条件中面积最大的。其中矩阵长为3宽为2,面积为6,也就是最后的答案。

【数据规模】

对于30%的数据 0<n m<=50

对于100%的数据 0<n m<=200

对于所有数据 a[i][j]<=20000000