这个问题姑且也叫做最大子矩阵吧
给一个树状图，求一个最大面积的子矩阵
思路是这样的，对于每个单位矩阵，求出左边连续不比它低的矩阵的下标，放在l数组里
同样，再求出右边连续的不比它低的矩阵的下标
这样，对于每个单个矩阵所能得到的最大面积就是 (r[i]-l[i]+1)*a[i]
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; const int maxn = + ;
long long a[maxn], l[maxn], r[maxn]; int main(void)
{
#ifdef LOCAL
freopen("1506in.txt", "r", stdin);
#endif long long n;
while(scanf("%I64d", &n) == && n)
{
long long ans = -;
long long i, t;
for(i = ; i <= n; ++i)
scanf("%I64d", &a[i]);
l[] = ;
r[n] = n;
for(i = ; i <= n; ++i)
{
t = i;
while(t > && a[i] <= a[t-])
t = l[t-];
l[i] = t;
}
for(i = n-; i > ; --i)
{
t = i;
while(t < n && a[i] <= a[t+])
t = r[t+];
r[i] = t;
}
long long temp;
for(i = ; i <= n; ++i)
{
temp = (r[i]-l[i]+)*a[i];
ans = max(ans, temp);
}
printf("%I64d\n", ans);
}
return ;
}
代码君