Cod sursa(job #1739142)

Utilizator Bulgaru_Robert_Razvan_323CBBulgaru Robert Razvan Bulgaru_Robert_Razvan_323CB Data 8 august 2016 18:10:11
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("scmax.in");
ofstream out("scmax.out");

vector<int> a;
unsigned int v[100003];
unsigned int p[100003];


unsigned int N,m,index;

void resolve() {
	v[N]=1;
	p[N]=-1;

	for (unsigned int i=N-1;i>=1;i--) {
		v[i]=1;
		p[i]=-1;

		for (unsigned int j=i+1;j<=N;j++) {
			if (a[i]<a[j] && v[i]<1+v[j]) {
				v[i]=1+v[j];
				p[i]=j;

				if (v[i]>m) {
					m=v[i];
					index=i;
				}
			}
		}
	}
}

int main() {
	in>>N;

	for (unsigned int i=0;i<N;i++) {
		int x;
		in>>x;
		a.push_back(x);
	}

	resolve();
	out<<max<<"\n";
	
	unsigned int i=index;
	while(i!=-1) {
		out<<a[f]<<" ";
		i=p[i];
	}

	return 0;
}