Cod sursa(job #1368265)

Utilizator ibicecIT Zilla ibicec Data 2 martie 2015 15:37:42
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main() {
	ifstream inp("scmax.in");
	ofstream out("scmax.out");

	int n;
	inp >> n;
	vector<int> a(n);

	for (int i=0; i<n; i++) {
		inp >> a[i];
	}

	int max = 1;
	int maxp = 0;
	vector<int> best(n, 1), s(n,-1);

	for (int i=0; i<n; i++) {
		for (int j=0; j<i; j++) {
			if ( best[j] > best[i]-1 && a[j] < a[i] ) {
				best[i] = 1 + best[j];
				s[i] = j;
				if ( best[i] > max ) { 
					maxp = i;
					max = best[i];
				}
			}
		}
	}

	out << max << endl;
	vector<int> r; 

	int p = maxp;
	while ( p != -1) {
		r.push_back(a[p]);
		p = s[p];
	}

	for (int i=max-1; i>=0; i--) {
		out << r[i] << " ";
	}

}