Cod sursa(job #1724653)

Utilizator Vbs96Vitelaru Sebastian Vbs96 Data 3 iulie 2016 19:23:56
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int  n,v[100001],p[100001],l[100001];

void afisare(int i)
{
	if (i != 0){
		afisare(p[i]);
		printf("%d ", v[i]);
	}
}
int main()
{
	int i, j,max=-1,poz_max;
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		scanf("%d", v + i);

	l[1] = 1;
	p[1] = 0;
	for (i = 2; i <=n; i++){

		l[i] = 1;
		p[i] = 0;
		for (j = 1; j <= i-1 ;j++)
			if (v[i] > v[j] && l[i]<l[j]+1 ){
				l[i] = l[j] + 1;
				p[i] = j;
			}
		if (l[i] >=max) { 
			max = l[i]; 
			poz_max = i; 
		}
	}


	printf("%d\n", max);
	afisare(poz_max);
	return 0;
}