Pagini recente » Cod sursa (job #2099143) | Cod sursa (job #566357) | Cod sursa (job #838231) | Cod sursa (job #1511967) | Cod sursa (job #2261395)
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int urm[100005], a[100005], lis[100005];
int n,i,j,maxim,ind,lmax,imax;
int main()
{
fin>>n;
for(i=1;i<=n;i++)
fin>>a[i];
urm[n]=0;
lis[n]=1;
for(i=n-1;i>=1;i--)
{
lmax=0;
ind=0;
for(j=i+1;j<=n;j++)
if(a[i]<a[j]&&lis[j]+1>lmax)
{
lmax=lis[j]+1;
ind=j;
}
if(lmax==0)
{
lis[i]=1;
urm[i]=0;
}
else
{
lis[i]=lmax;
urm[i]=ind;
}
if(lis[i]>maxim)
maxim=lis[i],imax=i;
}
/*for(i=1;i<=n;i++)
fout<< a[i] << ' ';
fout<< '\n';
for(i=1;i<=n;i++)
fout<< lis[i] << ' ';
fout<< '\n';
for(i=1;i<=n;i++)
fout<< urm[i] << ' ';
fout<< '\n';*/
fout<< maxim << '\n';
fout<< a[imax] << ' ' ;
i=imax;
while(urm[i])
{
fout<< a[urm[i]] << ' ';
i=urm[i];
}
fout<< '\n';
return 0;
}