Cod sursa(job #978617)

Utilizator TibixbAndrei Tiberiu Tibixb Data 29 iulie 2013 11:58:29
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#define INF 2000000001

using namespace std;

int v[100010];
int d[100010];
int sol[100010];
int t[100010];
int n, i, maxim, j, k, pmaxim;

int main() {
	
	ifstream fin("scmax.in");
	ofstream fout("scmax.out");
	fin>>n;
	for (i=1;i<=n;i++) {
		fin>>v[i];
	}
	
	d[1] = 1;
	v[++n] = INF;
	for (i=2;i<=n;i++) {
		maxim = 0;
		pmaxim = 0;
		for (j=1;j<i;j++)
			if (v[j] < v[i] && d[j] > maxim) {
				maxim = d[j];
				pmaxim = j;
			}
		d[i] = maxim + 1;
		t[i] = pmaxim;
	}
	
	i = n;
	while (i != 0) {
		sol[++k] = v[i];
		i = t[i];
		
	}
	
	fout<<d[n]-1<<"\n";
	for (i=k;i>=2;i--)
		fout<<sol[i]<<" ";
	return 0;
}