Pagini recente » Cod sursa (job #2612399) | Cod sursa (job #1086815) | Cod sursa (job #1744704) | Cod sursa (job #283113) | Cod sursa (job #1466561)
#include <cstdio>
#include <algorithm>
#define Dim 100003
FILE * f = fopen("scmax.in", "r");
FILE * g = fopen("scmax.out", "w");
using namespace std;
int n, i, best[Dim], poz[Dim], p, a[Dim], maxx;
void read()
{
fscanf(f, "%d", &n);
for(i = 1; i <= n; ++ i)
fscanf(f, "%d", &a[i]);
}
void DP()
{
int i, j;
best[n] = 1;
poz[n] = -1;
p = n;
maxx = 1;
for(i = n - 1; i >= 1; -- i)
{
best[i] = 1;
poz[i] = -1;
for(j = i + 1; j <= n; j ++)
if(a[j] > a[i] && best[i] < best[j] + 1)
{
best[i] = best[j] + 1;
poz[i] = j;
if(maxx < best[i])
maxx = best[i], p = i;
}
}
}
void build()
{
int i;
i = p;
while(i != -1)
{
fprintf(g, "%d ", a[i]);
i = poz[i];
}
}
int main()
{
read();
DP();
fprintf(g, "%d\n", maxx);
build();
return 0;
}