Pagini recente » Cod sursa (job #2866044) | Cod sursa (job #2631691) | Cod sursa (job #2632641) | Cod sursa (job #1472095) | Cod sursa (job #239764)
Cod sursa(job #239764)
#include<fstream>
using namespace std;
ifstream f ("scmax.in");
ofstream g ("scmax.out");
int DP(long v[], long n, long subsir[])
{
long lungime,inceput,i,j;
long *maxime=new long[n];
long *urmatorul=new long[n];
maxime[n-1] = 1;
urmatorul[n-1] =-1;
for(i=n-2;i>=0;i--)
{
maxime[i] = 1;
urmatorul[i] =-1;
for(j=n-1;j>i;j--)
if((v[i]<v[j])&&(maxime[i]<=maxime[j])) maxime[i]=maxime[j]+1,urmatorul[i]=j;
}
lungime = maxime[0];
inceput = 0;
for(i=1;i<n;i++)
if(lungime<maxime[i]) lungime=maxime[i],inceput=i;
subsir[0] = v[inceput];
for(i=1;i<lungime;i++) inceput=urmatorul[inceput],subsir[i]=v[inceput];
return lungime;
}
int main()
{
long n,x;
f>>n;
long *v=new long[n];
long *s=new long[n];
for(int i=0;i<n;i++) f>>v[i];
x=DP(v,n,s);
g<<x<<"\n";
for(int i=0;i<x;i++) g<<s[i]<<" ";
f.close();
g.close();
return 0;
}