Cod sursa(job #696800)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 28 februarie 2012 20:10:09
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <cstdio>

long N, i, j, lgmax, pos, max, posm, a[5001], b[5001], c[5001], d[5001];

int main() {
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w", stdout);
	
		scanf("%ld", &N);
		
		for (i = 1; i <= N; ++i)
			scanf("%ld", &a[i]);
		c[N] = N;
		max = 0;
		for (i = N; i > 0; --i) {
			lgmax = 0;
			pos = i;
			for (j = i+1; j <= N; ++j) {
				if (a[j] > a[i] && b[j]+1 > lgmax) {
					lgmax = b[j]+1;
					pos = j;
				}
			}
			
			b[i] = lgmax;
			c[i] = pos;
			if (lgmax > max) {
				max = lgmax;
				posm = i;
			}
		}
		
		printf("%ld\n", max+1);
		while (posm != c[posm]) {
			printf("%ld ", posm);
			posm = c[posm];
		}
		printf("%ld\n", posm);
	
	return 0;
}