Cod sursa(job #1246614)

Utilizator dinuandAndrei-Mario Dinu dinuand Data 21 octombrie 2014 13:13:12
Problema Subsir crescator maximal Scor 65
Compilator c Status done
Runda Arhiva educationala Marime 1.13 kb
#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;
}