Pagini recente » Cod sursa (job #1560867) | Cod sursa (job #2647249) | Cod sursa (job #1538386) | Cod sursa (job #2389775) | Cod sursa (job #454833)
Cod sursa(job #454833)
#include <cstdio>
#define file_in "scmax.in"
#define file_out "scmax.out"
int n,v[101000],best[101000],poz[101000],max,p;
void citire()
{
int i;
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d", &n);
for (i=1;i<=n;++i)
scanf("%d", &v[i]);
}
void scrie()
{
int i;
i=p;
while (i!=-1)
{
printf("%d ", v[i]);
i=poz[i];
}
}
void solve()
{
int i,j;
best[n]=1;
poz[n]=-1;
for (i=n-1;i>=1;--i)
{
best[i]=1;
poz[i]=-1;
for (j=i+1;j<=n;++j)
if (v[i]<v[j] && best[i]<best[j]+1)
{
best[i]=best[j]+1;
poz[i]=j;
}
if (best[i]>max)
max=best[i],
p=i;
}
printf("%d\n", max);
scrie();
}
int main()
{
citire();
solve();
fclose(stdin);
fclose(stdout);
return 0;
}