Pagini recente » Istoria paginii utilizator/mihaita_bog | Cod sursa (job #1500539) | Cod sursa (job #611909) | Cod sursa (job #2672364) | Cod sursa (job #1246614)
#include <stdio.h>
#define MAXN 100001
#define INF 0x3f3f3f3f
int n, v[MAXN], Best[MAXN], Pre[MAXN];
void build_solution(int pos, FILE *fdout)
{
if (Pre[pos] == 0) {
fprintf(fdout, "%d ", v[pos]);
return;
} else {
build_solution(Pre[pos], fdout);
fprintf(fdout, "%d ", v[pos]);
}
}
int main()
{
FILE *fdin = fopen("scmax.in", "r");
FILE *fdout = fopen("scmax.out", "w");
fscanf(fdin, "%d", &n);
int i;
for (i = 0; i < n; i++) fscanf(fdin, "%d", &v[i]);
/** the length of the optimal increasing subsequence
* that ends in the first at index 0
*/
Best[0] = 1;
Pre[0] = 0;
int max_length, j, pos;
for (i = 1; i < n; i++) {
max_length = 0;
for (j = 0; j < i; j++) {
if (v[j] < v[i]) {
if (Best[j] > max_length) {
max_length = Best[j];
pos = j;
}
}
if (max_length) {
Best[i] = max_length + 1;
Pre[i] = pos;
} else {
Best[i] = 1;
Pre[i] = 0;
}
}
}
max_length = 0;
for (i = 0; i < n; i++)
if (Best[i] > max_length) {
max_length = Best[i];
pos = i;
}
fprintf(fdout, "%d\n", max_length);
build_solution(pos, fdout);
fclose(fdin);
fclose(fdout);
return 0;
}