Pagini recente » Cod sursa (job #1632007) | Cod sursa (job #1966701) | Cod sursa (job #2218402) | Borderou de evaluare (job #1551132) | Cod sursa (job #1739797)
#include <fstream>
#define NMAX 100001
using namespace std;
int a[NMAX];
int n;
int B[NMAX];
int s[NMAX];
int l;
int P[NMAX];
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int calculB ()
{
B[1]=1;
P[1]=0;
int i, j, max, maxl;
for(i=2; i<=n; i++)
{
max=0;
P[i]=0;
for(j=1; j<=i-1; j++)
if(a[j]<a[i] && max<B[j])
{
max=B[j];
P[i]=j;
}
B[i]=max+1;
}
max=0;
for(i=1;i<=n;i++)
if(B[i]>max)
max=B[i], maxl=i;
return maxl;
}
void construire ()
{
int m, i, k;
//calculez indicele celui mai lung subsir
m=1;
for(i=2; i<=n; i++)
if(B[i]>B[m])
m=i;
k=B[m];
l=k;
s[k]=a[m];
while(P[m]>0)
{
m=P[m];
k--;
s[k]=a[m];
}
}
void afisare (int l)
{
int i;
fout<<l-1<<'\n';
for(i=1;i<=l-1;i++)
fout<<s[i]<<' ';
}
int main()
{
fin>>n;
int i;
for(i=1; i<=n; i++)
fin>>a[i];
int lung=calculB();
construire();
afisare(lung-1);
return 0;
}