Pagini recente » Borderou de evaluare (job #869929) | Cod sursa (job #808807)
Cod sursa(job #808807)
#include <fstream>
using namespace std;
int v[100000],i,n,lgmax[100000],maxc,j,urm[100000],jmax;
int main()
{
ifstream f("sir.in");
ofstream g("sir.out");
f>>n;
for (i=0;i<n;i++)
{
f>>v[i];
}
lgmax[n-1]=1;
for (i=n-2;i>=0;i--)
{
maxc=1;
jmax=-1;
for (j=1;j+i<=n-1;j++)
{
if (v[i]<v[j+i])
{
if (maxc<=lgmax[j+i]+1)
maxc=lgmax[j+i]+1,jmax=j+i;
}
}
lgmax[i]=maxc;
urm[i]=jmax;
}
maxc=0;
for (i=0;i<n;i++)
if (maxc<=lgmax[i])
maxc=lgmax[i],jmax=i;
g<<maxc<<'\n'<<v[jmax]<<' ';
while (urm[jmax]!=-1)
{
g<<v[urm[jmax]]<<' ';
jmax=urm[jmax];
}
f.close();
g.close();
return 0;
}