tle了我几个月.......谢谢cqf大牛的算法。

//State: 0.22s 1512kb

//用l,r两个数组保存当前元素向左向右访问能够达到的最大下标，因此可用dp

//另：此题甚bt，数据量大的惊人，而且有陷阱，必须用scanf。我用cin的时候起码读了10s.........

#include <cstdio>

int a[100000], l[100000], r[100000], n;

int main()
{
 freopen("in.txt", "r", stdin);
 while(scanf("%d", &n) && n)
 {
  int i;
  double max = 0.00;
  for(i = 0; i < n; i ++)
  {
   scanf("%d", &a[i]);     
  }
  for(i = 0; i < n; i ++)
  {
   l[i] = i;
   while(l[i] > 0 && a[i] <= a[l[i] - 1])
   {
    l[i] = l[l[i] - 1];
   }   
  }
  //pl();
  for(i = n - 1; i >= 0; i --)
  {
   r[i] = i;
   while(r[i] < n - 1 && a[i] <= a[r[i] + 1])
   {
    r[i] = r[r[i] + 1];
   }
   double t = double((r[i] - l[i] + 1) * double(a[i]));
   if(max < t)
    max = t;
  }
  //pr();
  printf("%0.0f\n", max);
 }
 return 0;
}

评论