Pagini recente » Cod sursa (job #2470090) | Cod sursa (job #133651) | Cod sursa (job #2504518) | Cod sursa (job #1732063) | Cod sursa (job #2705966)
#include <fstream>
#define NMAX 100000
using namespace std;
int n;
int v[NMAX+3],dp[NMAX+3],prec[NMAX+3],sol[NMAX+3];
ifstream fin("scmax.in");
ofstream fout ("scmax.out");
int main()
{
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>v[i];
}
dp[1]=1;
prec[1]=0;
int maximDp=0,pozDp=0;
for(int i=2; i<=n; i++)
{
int maxim=1,poz=0;
for(int j=1; j<i; j++)
{
if(v[i]>v[j] && maxim<dp[j]+1)
{
maxim=dp[j]+1;
poz=j;
}
}
if(maximDp<maxim)
{
maximDp=maxim;
pozDp=i;
}
dp[i]=maxim;
prec[i]=poz;
}
int num=pozDp,elem=0;
while(num>0)
{
sol[++elem]=v[num];
num=prec[num];
}
fout<<maximDp<<endl;
for(int i=elem; i>=1; i--)
{
fout<<sol[i]<<" ";
}
return 0;
}