Pagini recente » Cod sursa (job #1703578) | Cod sursa (job #258643) | Cod sursa (job #650239) | Cod sursa (job #1075168) | Cod sursa (job #1168154)
#include <stdio.h>
using namespace std;
#define MAX 100000
long long v[MAX+1];
int best[MAX+1];
int next[MAX+1];
long long sol[MAX+1];
int main()
{
FILE *fin,*fout;
fin=fopen("scmax.in","r");
fout=fopen("scmax.out","w");
int i,n,ind,max,maxbest,indmax,j;
fscanf(fin,"%d",&n);
for(i=1;i<=n;i++)
fscanf(fin,"%lld",&v[i]);
best[1]=1;
maxbest=1;
ind=1;
for(i=2;i<=n;i++)
{
max=0;
for(j=i-1;j>=1;j--)
if(v[i]>v[j]&&best[j]>max)
{
max=best[j];
ind=j;
}
best[i]=max+1;
if(maxbest<best[i])
{
maxbest=best[i];
indmax=i;
}
next[i]=ind;
}
fprintf(fout,"%d\n",maxbest);
i=indmax;
j=maxbest+1;
while(next[i]!=0)
{
sol[--j]=v[i];
i=next[i];
}
if(i==1&&sol[1]==v[1])
sol[1]=v[1];
for(i=1;i<=maxbest;i++)
fprintf(fout,"%lld ",sol[i]);
return 0;
}