Pagini recente » Cod sursa (job #1641959) | Cod sursa (job #192310) | Cod sursa (job #138194) | Cod sursa (job #1425214) | Cod sursa (job #336655)
Cod sursa(job #336655)
#include<stdio.h>
#define N 100005
int v[N], best[N], maxim, n, i,max1=0;
int max(int poz)
{int sol=0, j, lo, hi, mid, soll=0;
lo=poz+1;
hi=n;
while(lo<=hi){
mid = lo + (hi-lo)/2;
if(v[mid]<v[poz])lo=mid+1;
else if(v[mid]>=v[poz]){
if(best[mid]>=sol){hi=mid-1;soll=mid;sol=best[mid];}
else return soll;}
}
return soll;
}
void dinamic()
{int k;
for(i=n;i>=1;--i)
{
k=max( i);
if(!k)best[i]=1;
else {
best[i]=best[k]+1;
if(best[i]>max1)
{
max1=best[i];
maxim=i;}}
}
}
void afisare()
{int k=best[maxim];
printf("%d\n",best[maxim]);
for(i=1;i<=n && k;i++)
if(best[i]==k){printf("%d ",v[i]);--k;}
}
int main()
{
freopen("scmax.in","r",stdin);
freopen("scmax.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
dinamic();
afisare();
return 0;
}