Cod sursa(job #942126)

Utilizator tudorv96Tudor Varan tudorv96 Data 20 aprilie 2013 21:21:48
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
#include <vector>
using namespace std;

#define in "scmax.in"
#define out "scmax.out"
#define N 100005

vector <int> v (N), D(N), t(N, -1);
int n, MAX = 0, dr = 0;

ofstream fout (out);

void Write (int x)
{
	if (t[x] != -1)
		Write (t[x]);
	fout << v[x] << " ";
}

int main ()
{
	ifstream fin (in);
	fin >> n;
	for (int i = 0; i < n; ++i) {
		fin >> v[i];
		D[i] = 1;
		for (int j = 0; j < i; ++j)
			if (v[j] < v[i] && D[j] + 1 > D[i]) {
				D[i] = D[j] + 1;
				t[i] = j;
			}
		if (D[i] > MAX) {
			MAX = D[i];
			dr = i;
		}
	}
	fin.close();
	fout << MAX << "\n";
	Write (dr);
	fout.close();
	return 0;
}