Cod sursa(job #596687)

Utilizator mihai.ortelecanOrtelecan Mihai alexandru mihai.ortelecan Data 18 iunie 2011 14:13:12
Problema Subsir crescator maximal Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 1.07 kb
/*
 * subsirCrescatorMaximal.c
 *
 *  Created on: Jun 18, 2011
 *      Author: mihai
 */

#include <stdio.h>
#define MAX 100001

int i, j, N, nr[MAX], dim[MAX], indici[MAX], ultim = 0, max = 0;

void afiseaza_numere(int i) {

	if (i == indici[i]) {
		printf("%d ", nr[i]);
		return;
	}
	afiseaza_numere(indici[i]);
	printf("%d ", nr[i]);
}

int main() {

	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);

	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &nr[i]);

	dim[0] = 1;
	indici[0] = 0;
	for (i = 1; i < N; i++) {
		if (nr[i] > nr[i - 1]) {
			dim[i] = dim[i - 1] + 1;
			indici[i] = i - 1;
			if (dim[i] >= max) {
				max = dim[i];
				ultim = i;
			}
		} else if (nr[i] == nr[i - 1]) {
			dim[i] = dim[i - 1];
			indici[i] = indici[i - 1];
		} else {
			j = i - 1;

			while (nr[i] < nr[j] && j != 0 && j != indici[j]) {
				j = indici[j];
			}
			if (j == 0 || j == indici[j]) {
				indici[i] = i;
				dim[i] = dim[j];
			} else {
				indici[i] = j;
				dim[i] = dim[j] + 1;
			}

		}
	}
	printf("%d\n", dim[ultim]);
	afiseaza_numere(ultim);
	return 0;
}