Cod sursa(job #345921)

Utilizator digital_phreakMolache Andrei digital_phreak Data 5 septembrie 2009 17:02:26
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <cstdlib>
#define MAXN 100010
using namespace std;

long A[MAXN],B[MAXN],pre[MAXN],N,LMax,p;

int main() {
	
	ios::sync_with_stdio(false);
	
	int i,j;
	
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	
	scanf("%d",&N);
	for (i=0;i<N;++i) {scanf("%d",&A[i]);pre[i] = -1;}
	
	B[N-1] = 1;
	for (i=N-1;i>0;--i) {
		B[i] = 1;
		for (j=i+1;j<N;++j) {
			if ((B[i] < B[j] + 1) && (A[i] < A[j])) {
				B[i] = B[j] + 1;
				pre[i] = j;
				if (B[i] > LMax) LMax = B[i],p = i;
			}
		}
	}
	
	i = 0;
	printf("%d\n",LMax);
	while (p != -1) {
		printf("%d ",A[p]);
		p = pre[p];
	}
	printf("\n");
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}