Pagini recente » Cod sursa (job #2842259) | Cod sursa (job #3174469) | Cod sursa (job #731060) | Cod sursa (job #2480937) | Cod sursa (job #238086)
Cod sursa(job #238086)
#include<fstream>
using namespace std;
ifstream f ("scmax.in");
ofstream g ("scmax.out");
long long v[100000],s[100000],n,x,maxime[100000],urmatorul[100000];
int DP(long long v[], long long n, long long subsir[])
{
long long lungime,inceput,i,j;
maxime[n-1] = 1;
urmatorul[n-1] =-1;
for(i=n-2;i>=0;i--)
{
maxime[i] = 1;
urmatorul[i] =-1;
for(j=i+1;j<n;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()
{
f>>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;
}