Cod sursa(job #528840)

Utilizator gabriela.rGabriela gabriela.r Data 3 februarie 2011 16:02:12
Problema Subsir crescator maximal Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>

long n, a[100001], lmax,poz, p[100001];
FILE *f,*g;

void citire() {
	long i;
	fscanf(f,"%ld", &n);
	for (i=1; i<=n; i++) fscanf(f,"%ld",&a[i]);
}

void det() {
	long i,j;
	p[n]=1;
	lmax=1; poz=n;
	for (i=n-1; i>=1; i--){
		j=i+1;
		while ((a[i]>=a[j])&&(j<=n)) j++;
		if (j>n) p[i]=1;
		else p[i]=p[j]+1;
		if (p[i]>lmax) {
			lmax=p[i];
			poz=i;
		}
	}
}

void scriere(){
	long i,x,pl;
	pl=lmax;
	fprintf(g,"%ld \n",lmax);
	i=poz;
	x=a[poz];
	fprintf(g,"%ld ",a[poz]);
	while (pl>1) {
		while ((p[i]!=pl-1)||(a[i]<=x)) i++;
		x=a[i];
		pl--;
		fprintf(g,"%ld ",x);
	}
}

int main(void){
	long i;
	f=fopen("scmax.in","r");
	g=fopen("scmax.out","w");
	citire();
	det();
	scriere();
	fclose(f);
	fclose(g);
	return 0;
}