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();
}                                     
      

Download