Cod sursa(job #668982)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 25 ianuarie 2012 22:12:44
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream>
#define NMAx 100100
using namespace std;
int v[NMAx],best[NMAx],drum[NMAx],n,poz,mx;
void afis() {
	ofstream out("scmax.out");
	out<<mx<<'\n';
	while(poz!=-1)
		{out<<v[poz]<<" ";
		poz=drum[poz];
		}
	out<<'\n';
	out.close();
}
void subsir() {
	int i,j;
	best[n-1]=1;
	drum[n-1]=-1;
	mx=1,poz=n-1;
	for(i=n-2;i>=0;i--) {
		best[i]=1;
		drum[i]=-1;
		for(j=i+1;j<n;j++)
			if(v[i]<v[j]&&best[i]<best[j]+1) {
				best[i]=best[j]+1;
				drum[i]=j;
				if(best[i]>mx)
					mx=best[i],poz=i;
				}
		}
}
void citire() {
	int i;
	ifstream in("scmax.in");
	in>>n;
	for(i=0;i<n;i++)
		in>>v[i];
	in.close();
}
int main() {
	citire();
	subsir();
	afis();
	return 0;
}