Cod sursa(job #664391)

Utilizator roxana_savulescuSavulescu Roxana roxana_savulescu Data 20 ianuarie 2012 01:00:39
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<fstream>
using namespace std;
long  i,j,max1,a[100005],b[100005],n,c[100005],p[100005],ix;
int main(){
	ifstream f("scmax.in");
	ofstream g("scmax.out");
	f>>n;
	for (i=1;i<=n;i++){
		f>>a[i];
		b[i]=1;
	}
	for (i=2;i<=n;i++){
		b[i]=1;
		for (j=i-1;j>=1;j--){
			if (a[i]>a[j] & b[j]+1>b[i]) {
				b[i]=b[j]+1;
				if (b[i]>max1){
                        max1=b[i];
						ix=i;
				}  
                p[i]=j;
			};
		}
	}
	g<<max1<<"\n";
	j=1;i=ix;
	while(i>0){
        c[j++]=a[i];
        i=p[i];
	}
	for (i=max1;i>=1;i--)
		g<<c[i]<<" ";
	g<<"\n";
	return 0;
}