Cod sursa(job #1426762)

Utilizator o_micBianca Costin o_mic Data 30 aprilie 2015 16:47:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#define infinity (1 << 29)
#define DN 105
#define LL long long
using namespace std;

int main() {
	int n, ind;
	LL x, res;
	vector <LL> v, l, p;
	stack <LL> s;
  	//freopen("input.txt", "r", stdin);
  	ifstream fin("scmax.in");
  	ofstream fout("scmax.out");
  	fin >> n; 
  	for(int i = 0; i < n; ++i){
  		fin >> x;
  		v.push_back(x);
  	}
  	l.push_back(1);
  	p.push_back(0);
  	res = 1;
  	ind = 0;
  	for(int i = 1; i < n; ++i){
  		int maxx = 1;
  		p.push_back(i);
  		for(int j = 0; j < i; ++j){
  			if(v[i] > v[j] && maxx < l[j] + 1){
  				maxx = l[j] + 1;
  				p[i] = j;
  			}
  		}
  		l.push_back(maxx);
  		if(maxx > res){
  			res = maxx;
  			ind = i;
  		}
  	}
  	fout << res << '\n'; 
  	while(p[ind] != ind){
  		s.push(ind);
  		ind = p[ind];
  	}
  	s.push(ind);
  	while(!s.empty()){
  		x = s.top();
  		s.pop();
  		fout << v[x] << ' ';
  	}
	return 0;
}