Cod sursa(job #413287)

Utilizator Mihai_OrtelecanOrtelecan Mihai Alexandru Mihai_Ortelecan Data 8 martie 2010 02:01:29
Problema Subsir crescator maximal Scor 65
Compilator c Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>
#include <stdlib.h>

int main(void) {

	FILE * fin = fopen("scmax.in", "r");
	FILE * fout = fopen("scmax.out", "w");

	long int n, i, j, sub_count = 0, IND = 0, k = 0;
	long int nr[100001], B[100001], S[100001], sol[100001];

	fscanf(fin, "%ld", &n);

	for (i = 0; i < n; i++) {
		fscanf(fin, "%ld", &nr[i]);
	}

	for (i = 0; i < n; i++) {

		B[i] = 1;
		S[i] = -1;

		for (j = i - 1; j >= 0; j--) {

			if (nr[j] < nr[i] && B[j] >= B[i]) {

				B[i] = B[j] + 1;
				S[i] = j;
			}
		}
		if (B[i] > sub_count) {
			sub_count = B[i];
		}
		if (nr[i] > IND && B[i] == sub_count) {
			IND = i;
		}
	}

	fprintf(fout, "%ld\n", sub_count);

	i = IND;

	while (i != -1) {
		sol[k] = nr[i];
		k++;
		i = S[i];
	}
	for (i = k - 1; i >= 0; i--) {
		fprintf(fout, "%ld ", sol[i]);
	}

	return 0;
}