KAGAIN - Chiến trường Ô qua
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
main()
{
long T,n,a[30001],left[30001],right[30001],r[30002],l[30002];
scanf("%ld",&T);
for(long i=1;i<=T;i++)
{
long max=0,x,y;
scanf("%ld",&n);
for(long j=1;j<=n;j++)
scanf("%ld",&a[j]);
long u=1;
r[1]=1;
while(r[u]!=n+1)
{
long t=r[u]+1;
if(a[t]<a[r[u]])
{
for(long j=u;j>=1;j--)
{
if(a[t]<a[r[j]])
{
right[r[j]]=t-1;
u--;
}
else
break;
}
u++;
r[u]=t;
}
else if(t==n)
{
for(long j=u;j>=1;j--)
right[r[j]]=n;
break;
}
else
{
u++;
r[u]=t;
}
}
right[n]=n;
u=1;
l[1]=n;
//printf("%ld %ld %ld %ld",right[4],right[3],right[2],right[1]);
while(l[u]!=0)
{
long t=l[u]-1;
if(a[t]<a[l[u]])
{
for(long j=u;j>=1;j--)
{
if(a[t]<a[l[j]])
{
left[l[j]]=t+1;
u--;
}
else
break;
}
u++;
l[u]=t;
}
else if(t==n)
{
for(long j=u;j>=1;j--)
left[l[j]]=n;
break;
}
else
{
u++;
l[u]=t;
}
}
left[1]=1;
//printf("%ld %ld %ld",left[4],left[3],left[2]);
for(long j=1;j<=n;j++)
if(a[j]*(right[j]-left[j]+1)>max)
{
max=a[j]*(right[j]-left[j]+1);
x=left[j];
y=right[j];
}
printf("%ld %ld %ld\n",max,x,y);
}
//getch();
}