Cod sursa(job #663991)

Utilizator zeeboBuzatu Vlad zeebo Data 19 ianuarie 2012 13:21:19
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int nr,max1,i,j,a[100001],b[100001],c[100001],n,poz;
int main ()
{
	f>>n;
	for (i=1;i<=n;i++) f>>a[i];
b[1]=1;
c[1]=1;
	for (i=2;i<=n;i++)
	{
		for (j=i-1;j>=1;j--)
			if (a[i]>a[j] && b[j]>b[i])
			{
				b[i]=b[j]+1;
				c[i]=j;
			}
		if (b[i]==0) {b[i]=1;c[i]=i;}
		if (b[i]>max1) {max1=b[i]; poz=i;}
	}
g<<max1<<'\n';
nr=max1+1;
for (i=poz;i>=1;i--)
	if (b[i]==nr-1) {g<<a[c[i]]<<' '; nr--;}
return 0;
}