Pagini recente » Cod sursa (job #1507365) | Cod sursa (job #2375551) | Cod sursa (job #3226265) | Cod sursa (job #1000077) | Cod sursa (job #1088954)
#include <fstream>
#define NMAX 100010
#define IN "scmax.in"
#define OUT "scmax.out"
using namespace std;
ifstream fin(IN);
ofstream fout(OUT);
int n;
int A[NMAX],b[NMAX],tata[NMAX];
void citire()
{
int i;
fin>>n;
for(i=1; i<=n; i++)
fin>>A[i];
}
void rezolva()
{
int i,maxi=0,poz,j;
for(i=1; i<=n; i++)
{
b[i]=1;
tata[i]=i;
}
for(i=2; i<=n; i++)
{
maxi=1;
poz=i;
for(j=1; j<i; j++)
if(A[i]>A[j])
if(maxi<(b[j]+1))
{
maxi=b[j]+1;
poz=j;
}
b[i]=maxi;
tata[i]=poz;
}
}
void afisare()
{
int i,maxi=0,poz,sol[NMAX],x;
for(i=1; i<=n; i++)
if(maxi<b[i]) {maxi=b[i];poz=i;}
fout<<maxi<<'\n';
for(x=1;x<=maxi;x++)
{
sol[x]=A[poz];
poz=tata[poz];
}
for(x=maxi;x>1;x--) fout<<sol[x]<<' ';fout<<sol[1];
}
int main()
{
citire();
rezolva();
afisare();
return 0;
}