Pagini recente » Cod sursa (job #1166836) | Cod sursa (job #1182844) | Cod sursa (job #21990) | Cod sursa (job #1794563) | Cod sursa (job #741956)
Cod sursa(job #741956)
#include <cstdio>
#include <iostream>
using namespace std;
#define maxN 100005
int best[maxN] , sol[maxN] , x[maxN] , tata[maxN];
int best_max , poz , poz_max , dim , N , sol_max;
int main ()
{
freopen ("scmax.in" , "r" , stdin);
freopen ("scmax.out" , "w" , stdout);
scanf ("%d" , &N);
for (int i = 1 ; i <= N ; ++i)
{
scanf ("%d" , &x[i]);
best_max = 0;
for (int j = 1 ; j < i ; ++j)
if (best[j] > best_max && x[j] < x[i])
{
best_max = best[j];
tata[i] = j;
}
best[i] = best_max + 1;
if (best[i] > sol_max)
{
sol_max = best[i];
poz_max = i;
}
}
printf ("%d\n" , sol_max);
for (int i = poz_max ; i >= 1 ; i = tata[i])
sol[++dim] = x[i];
for (int i = dim ; i >= 1 ; --i)
printf ("%d " , sol[i]);
return 0;
}