Pagini recente » Cod sursa (job #2051567) | Cod sursa (job #3032912) | Cod sursa (job #978068) | Salvare | Cod sursa (job #238082)
Cod sursa(job #238082)
#include<fstream>
using namespace std;
ifstream f ("scmax.in");
ofstream g ("scmax.out");
int DP(long long v[], long long n, long long subsir[])
{
long long lungime,inceput,i,j;
long long *maxime = new long long[n];
long long *urmatorul = new long 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=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];
}
delete urmatorul;
delete maxime;
return lungime;
}
int main()
{
long long v[100],n,s[100],x;
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;
}