HDU-6957 Maximal submatrix

HDU-6957 Maximal submatrix

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;
#define MXN 2010
int n, m, ans;
int v[MXN][MXN], h[MXN][MXN], l[MXN][MXN], r[MXN][MXN];
int main()
{
    int t, tmp;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        ans = m; // 单独一行肯定满足要求
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                scanf("%d", v[i] + j);
            }
        }   
        for (int i = 1; i <= m; ++i)        // 第1行初值
        {
            l[1][i] = 0, h[1][i] = 1, r[1][i] = m + 1;
        }
        // left, 从左向右递推，处理高度和左边界
        for (int  i = 2 ; i <= n ; ++i)
        {
            tmp = 0; // 左侧最近不满足"非递减"的位置，初始值0
            for (int j = 1 ; j <= m ; ++j)
            {                               // 判断区域是否可合并分别处理
                if (v[i][j] >= v[i - 1][j]) // 两个区域可合并，处理左边界和高度
                {
                    l[i][j] = max(l[i - 1][j] , tmp) , h[i][j] = h[i - 1][j] + 1;
                }
                else                        // 两个区域不可合并
                {
                    tmp = j , l[i][j] = 0 , h[i][j] = 1; 
                }
            }
        }
        // right，从右向左递推，处理右边界并计算面积
        for (int i = 2; i <= n; ++i)
        {
            tmp = m + 1; // 右侧最近不满足"非递减"的位置，初始值m+1
            for (int j = m; j >= 1; --j)
            { 
                if (v[i][j] >= v[i - 1][j])
                {
                    r[i][j] = min(r[i - 1][j], tmp);    // 判断区域是否可合并分别处理
                }
                    
                else
                {
                    tmp = j, r[i][j] = m + 1;
                }
                ans = max(ans, (r[i][j] - l[i][j] - 1) * h[i][j]); //求面积的最大
            }
        }
        printf("%d\n", ans); 
    }
    return 0;
}