Cod sursa(job #562529)

Utilizator KosmynC64Munteanu Cosmin KosmynC64 Data 23 martie 2011 11:44:53
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<iostream>
#include<fstream>
#include<vector>
#define N (int)v.size()
using namespace std;
int n,d,m,mi;
int a,oa;
vector<int> v;
vector<int> scmax;
int dp(int i){
	int max=0,max_i,dummy;
	if(scmax[i]==-1){
	for(int j=i+1;j<N;j++)
	if(v[i]<v[j]){
		dummy=dp(j);
		if(dummy>max)max=dummy;}
	scmax[i]=1+max;}
	return scmax[i];}
int main(){
	ifstream f("scmax.in");
	ofstream g("scmax.out");
	f>>n;
	scmax.resize(n,-1);
	for(;n;n--){
		f>>d;
		v.push_back(d);}
	
	for(int i=1;i<N;i++){
		d=dp(i);
		if(d>m){m=d;mi=i;}}
		
	oa=-2;
	g<<scmax[mi]<<'\n';
	for(int i=mi;i<N;i++){
		a=scmax[i];
		if(oa!=a)g<<v[i]<<' ';
		oa=a;}
		
	f.close();g.close();
return 0;}