Cod sursa(job #579744)

Utilizator unsilviuContvechidontdeactivatepls unsilviu Data 12 aprilie 2011 13:59:17
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
using namespace std;
int v[100001],poz[100001],r[100001],size[100001];
int main() {
	FILE *f;
	f=fopen("scmax.in","r");
	ofstream g("scmax.out");
	int i,n,j,mx,pozmx,m,M;
	M=0;
	fscanf(f, "%d", &n);
	for (i=1; i<=n; i++)
		fscanf(f, "%d", &v[i]);
	for (i=2; i<=n; i++) {
		mx=0;
		pozmx=0;
		for (j=i-1; j>=1; j--)
			if (v[j]>mx&&v[j]<v[i]) {
				mx=v[j];
				pozmx=j;
			}
		poz[i]=pozmx;
		size[i]=size[pozmx]+1;
		if (size[i]>M) {
			M=size[i];
			m=i;
		}
	}
	j=m;
	g<<M<<'\n';
	for (i=0; i<=M; i++) {
		r[i+1]=v[j];
		j=poz[j];
	}
	for (i=M; i>=1; i--)
		g<<r[i]<<' ';
	g.close();
	return 0; }