Cod sursa(job #497457)

Utilizator uhraurhuavasile paul emilian uhraurhua Data 2 noiembrie 2010 16:25:25
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<iostream>
#include<fstream>
#include <vector>
using namespace std;
ifstream p("scmax.in");
ofstream v("scmax.out");
const int MAX_N = 10005;

int n, a[MAX_N], c[MAX_N],max2=0,k;

vector <int> vect;

int main(){
	p>>n;
	for(int i=1;i<=n;i++)
		p>>a[i];
	for(int i=1;i<=n;i++) {
		c[i] = 1;
		for(int j=i-1;j>=1;j--)
			if(a[i] > a[j]) 
				if (c[i] < c[j] + 1)
					c[i] = c[j] + 1;
		
	}
	for(int i=1;i<=n;i++)
		if(c[i]>max2){
			max2=c[i];
			k=i;
		}
	vect.push_back(a[k]);
	// cout<<a[k]<<" ";
	//for(int i=k;i>1;i--)
	int i=k;
	while(i>1){
		for(int j=k-1;j>=1;j--)
		if(c[i]>c[j] && a[i]>a[j] && c[j]<max2){
			vect.push_back(a[j]);
			// cout<<a[j]<<" ";
			i--;
			max2=c[j];
		}
		i--;
	}
		//v<<c[k]<<" "<<a[k]<<endl;
		v<<vect.size()<<endl;
	for (int i = (int)vect.size() - 1; i >= 0; -- i)
		v << vect[i] << " ";
	return 0;
}