Cod sursa(job #797494)

Utilizator gabriela95Andreea Gabriela gabriela95 Data 14 octombrie 2012 10:49:04
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,i,j,maxim,nrmaxim,v[100001],l[100001],pozmaxim,poz,t[100001],p,u[100001];
int main()
{
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];nrmaxim=1;
	for(i=1;i<=n;i++)
	{
		maxim=0;
		for(j=1;j<=i-1;j++)
			if(v[j]<v[i]&&maxim<l[j]){
				maxim=l[j];
				poz = j;
			}
		l[i]=1+maxim;
		if (l[i] > 1)
			t[i] = poz;
		if(l[i]>nrmaxim) {
			nrmaxim=l[i];
			pozmaxim = i;
		}
	}
	g<<nrmaxim<<"\n";
	while (pozmaxim!=0) {
		u[++p]=v[pozmaxim];
		pozmaxim = t[pozmaxim];
	}
	for(i=p;i>=1;i--)
		g<<u[i]<<" ";
	return 0;
}