Cod sursa(job #721548)
#include <fstream>
using namespace std;
#define nmax 100001
ifstream f ("scmax.in");
ofstream g ("scmax.out");
int best[nmax],poz[nmax],a[nmax],l[nmax],n,max;
int cauta(int i)
{
int max=0,p=0,j;
for(j=1;j<i;j++)
if(max<best[j] && a[j]<a[i]) max=best[j],p=j;
return p;
}
void dinamic()
{
int i;
best[1]=1;
for(i=2;i<=n;i++)
{
int p;
p=cauta(i);
best[i]=best[p]+1;
poz[i]=p;
}
}
void afisare2(int p)
{
if(poz[p]>0) {afisare2(poz[p]);}
g<<a[p]<<" ";
}
void afisare()
{
int max=0,p=0,i;
for(i=1;i<=n;i++)
{
if(max<best[i]) max=best[i],p=i;
}
g<<max<<"\n";
afisare2(p);
g.close();
}
int main()
{
int i;
f>>n;
for(i=1;i<=n;i++) f>>a[i];
f.close();
dinamic();
afisare();
return 0;
}