Cod sursa(job #627349)

Utilizator sebii_cSebastian Claici sebii_c Data 29 octombrie 2011 17:33:34
Problema Subsir crescator maximal Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 0.72 kb
#include <stdio.h>
#define NMAX 100010

int A[NMAX], pre[NMAX], len[NMAX], poz, max;
int n;

void lcim()
{
    int i, j;
    len[n] = 1;
    pre[n] = -1;
    for (i=n-1; i>=1; --i) {
	len[i] = 1;
	pre[i] = -1;
	for (j=i+1; j<=n; ++j)
	    if (A[i] < A[j] && len[i] < len[j] + 1) {
		len[i] = len[j] + 1;
		pre[i] = j;
		if (len[i] > max) {
		    max = len[i];
		    poz = i;
		}
	    }
    }
}

int main()
{
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);
    int i;
    scanf("%d", &n);
    for (i=1; i<=n; ++i) 
	scanf("%d", &A[i]);
    lcim();
    i = poz;
    printf("%d\n", max);
    while (i != -1) {
	printf("%d ", A[i]);
	i = pre[i];
    }
    return 0;
}