Cod sursa(job #900212)

Utilizator DanutsDanut Rusu Danuts Data 28 februarie 2013 18:16:59
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<stdio.h>
using namespace std;
#define maxn 500000
long long int a[maxn],poz,n,lg[maxn],maxx,maxim;
void read(){
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
}
void scmax(){
	lg[n]=1;
	for(int i=n-1;i>=1;--i){
		maxx=0;
		for(int j=i+1;j<=n;j++)
			if(a[i]<a[j])
				if(maxx<lg[j])
					maxx=lg[j];
		lg[i]=maxx+1;
		if(maxim<lg[i]){
			maxim=lg[i];
			poz=i;
		}
	}
}
void afis(){
	printf("%d\n",maxim);
	for(int i=1;i<=n;i++){
		if(lg[i]==maxim && a[i]>=a[poz]){
			printf("%d ",a[i]);
			maxim--;
			poz=i;}
	}
}
int main (){
	read();
	scmax();
	afis();
	return 0;}