Pagini recente » Cod sursa (job #2723635) | Cod sursa (job #1699556) | Cod sursa (job #868205) | Istoria paginii despre-infoarena | Cod sursa (job #1657744)
#include <cstdio>
using namespace std;
const int NMAX = 100003;
int best[NMAX], a[NMAX], poz[NMAX];
int _max, p, n;
void read()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
}
void dinamica()
{
int i, j;
best[n] = 1;
poz[n] = -1;
_max = 1; p = n;
for (i = n - 1; i >= 1; --i){
best[i] = 1;
poz[i] = -1;
for (j = i + 1; j <= n; ++j)
if (a[i] < a[j] && best[i] < best[j] + 1){
best[i] = best[j] + 1;
poz[i] = j;
if (best[i] > _max)
_max = best[i], p = i;
}
}
}
void constr()
{
int i = p;
while (i != -1){
printf("%d ", a[i]);
i = poz[i];
}
}
int main()
{
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
read();
dinamica();
printf("%d\n", _max);
constr();
return 0;
}