KPLANK - Bán dừa
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
#include <algorithm>
//#include <conio.h>
#define Max 1111111
using namespace std;
int T,n,k,a[Max],left[Max],right[Max],r[Max],l[Max];
int main()
{
scanf("%d",&n);
for(int j=1;j<=n;j++)
scanf("%d",&a[j]);
int u = 1;
r[1] = 1;
for(int i = 2;i<=n;i++){
if(a[i]<a[r[u]]){
while(a[i]<a[r[u]] && u>0){
right[r[u]] = i-1;
u--;
}
}
r[++u] = i;
if(i==n) for(int j = 1;j<=u;j++) right[r[j]] = n;
}
u = 1;
l[1] = n;
for(int i = n-1;i>0;i--){
if(a[i]<a[l[u]]){
while(a[i]<a[l[u]] && u>0){
left[l[u]] = i+1;
u--;
}
}
l[++u] = i;
if(i==1) for(int j = 1;j<=u;j++) left[l[j]] = 1;
}
//printf("%ld %ld %ld",left[4],left[3],left[2]);
int kq = 0;
for(int j=1;j<=n;j++)
{
if(a[j]<=right[j]-left[j]+1)
kq = max(kq,min(right[j]-left[j]+1,a[j]));
}
printf("%d",kq);
//getch();
}