Pagini recente » Cod sursa (job #679890) | Cod sursa (job #1153014) | Cod sursa (job #283718) | Cod sursa (job #1630051) | Cod sursa (job #2114595)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
const int N=100005;
int a[N],d[N],n,inceput[N];
int maxim;
void sol(int x)
{
if(x!=0)
sol(inceput[x]);
if(x>0)
out<<a[x]<<" ";
}
int main()
{
int poz,i,j,x,y;
/*
dp[i] = lungimea celui mai lung subsir crescator care se termina pe pozitia i
dp[i] = 1 + max {dp[j] | j < i si v[j] < v[i]}
*/
in>>n;
for(i=1; i<=n; i++)
{
in>>a[i];
d[i]=1;
}
for(i=2; i<=n; i++)
{
for(j=1; j<i; j++)
{
if(a[i]>a[j] && d[i]<d[j]+1)
{
d[i]=1+d[j];
inceput[i]=j;
}
}
}
for(i=1; i<=n; i++)
if(d[i]>maxim)
{
maxim=d[i];
poz=i;
}
out<<maxim<<'\n';
sol(poz);
return 0;
}