Cod sursa(job #628511)

Utilizator giuliastefGiulia Stef giuliastef Data 1 noiembrie 2011 16:50:06
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
//cel mai lung subsir crescator

#include <fstream>
#define NMAX 100001
using namespace std;
int n, v[NMAX], d[NMAX], sol[NMAX], maxim, pos;

void read(){
	int i;
	ifstream f("scmax.in");
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
}
void solve() {
	int i,j;
	d[1]=1;
	for(i=2;i<=n;i++)
	{
		d[i]=1;
		for(j=1;j<i;j++)
			if(v[j] < v[i] && d[j]+1 > d[i])
				d[i]=d[j]+1;
		if(d[i]>maxim) maxim=d[i], pos=i;	
	}
}
void write() {
	int i,k;
	ofstream g("scmax.out");
	g<<maxim<<"\n";
	k=1;
	sol[k]=v[pos];
	for(i=pos-1;i>=1;i--) {
		if(v[pos]>v[i] && d[pos]==d[i]+1)
			pos=i, sol[++k]=v[pos];
	}
	for(i=maxim;i>=1;i--)
		g<<sol[i]<<" ";
	
}
int main(){
	read();
	solve();
	write();
	return 0;
}