Problem Description
Given a matrix of n rows and m columns,find the largest area submatrix which is non decreasing on each column
Input
The first line contains an integer T(1≤T≤10)representing the number of test cases.
For each test case, the first line contains two integers n,m(1≤n,m≤2∗103)representing the size of the matrix
the next n line followed. the i-th line contains m integers vij(1≤vij≤5∗103)representing the value of matrix
It is guaranteed that there are no more than 2 testcases with n∗m>10000
Output
For each test case, print a integer representing the Maximal submatrix
Sample Input
1 2 3 1 2 4 2 3 3
Sample Output
4
\(n^2\)DP,设dp[i, j]为mtx[i, j]为右下角的最大的满足题意的子矩阵大小。按行遍历再按列遍历,对于(i, j)这个位置,首先求出来这一列以(i, j)结尾的最长单调不减序列的长度(维护一个数组mx即可)。然后再重新遍历第i行对mx数组跑单调栈更新dp[i, j]即可。
比如对于:
1 2 2 3 2 1 3 4 5 2 2 4
第三行的mx数组为[3, 2, 1, 3],则dp[3, 1] = 3,dp[3, 2] = 4, dp[3, 3] = 3,dp[3, 4] = 4。
#include <bits/stdc++.h> using namespace std; #define int long long int mtx[2005][2005], n, m; int dp[2005][2005], mx[2005], s[2005], w[2005]; signed main() { ios::sync_with_stdio(false); int t; cin >> t; while(t--) { cin >> n >> m; memset(dp, 0, sizeof(dp)); memset(mx, 0, sizeof(mx)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { dp[i][j] = 1; } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> mtx[i][j]; } } int ans = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) {//dp[i][j]表示i, j结尾的最大的满足条件的子矩阵 if(mtx[i][j] >= mtx[i - 1][j]) { mx[j]++; } else { mx[j] = 1; } } //mx[1 ~ j]从中选一个连续子区间l, r,设区间最小值为mn,怎么选使得mn * (r - l + 1)最大 //单调栈 int p; mx[m + 1] = p = 0; s[0] = s[1] = 0; w[0] = w[1] = 0; for(int j = 1; j <= m + 1; j++) { if(mx[j] > s[p]) { s[++p] = mx[j]; w[p] = 1; } else { int width = 0; while(s[p] > mx[j]) { width += w[p]; dp[i][j] = max(dp[i][j], width * s[p]); ans = max(ans, dp[i][j]); p--; } s[++p] = mx[j], w[p] = width + 1; } } } cout << ans << endl; } return 0; }