Cod sursa(job #749890)

Utilizator StrajanStrajan Sebastian Ioan Strajan Data 19 mai 2012 15:07:49
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
using namespace std;
#define MAX 100005

int main(){
	int x[MAX], a[MAX], c[MAX];
	int p, max, i, k, n;
	
	ifstream fin("scmax.in");
	ofstream fout("scmax.out");
	fin>>n;
	for (i=1; i<=n; i++) fin>>x[i];
	max = 1;
	p = n;
	c[n] = 1;
	for (k=n-1; k>0; k--){
		c[k] = 1; a[k] = 0;
		for (i=k+1; i<=n; i++)
			if (x[i]>x[k])
				if (c[i]+1>c[k]){
					c[k] = c[i]+1;
					a[k] = i;
				}
			if (c[k]>max){
				max = c[k];
				p = k;
			}
	}
	fout<<max<<"\n";
	fout<<x[p]<<" ";
	for (i=1; i<max; i++){
		p = a[p];
		fout<<x[p]<<" ";
	}
	fin.close();
	fout.close();
	
	return 0;
}