Cod sursa(job #1452551)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 21 iunie 2015 12:28:07
Problema Subsir crescator maximal Scor 60
Compilator c Status done
Runda Arhiva educationala Marime 1.22 kb
#include <stdio.h>
#include <stdlib.h>
#define MAX 100005

typedef struct cel{
	int info;
	struct cel* urm;
} TCel, *TLista, **ALista;

int ins(ALista L, int x);
int copy(ALista Ls, ALista Ld);
void AfiL(TLista L);

int main(){
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	int n, i, j, maxim, nr[MAX];
	int v[MAX];
	TLista L[MAX];
	scanf("%d", &n);
	for(i = 0; i < n; i++)
		scanf("%d", &v[i]);

	for(i = 0; i < n; i++){
		L[i] = NULL;
		nr[i] = 1;
		ins(&L[i], v[i]);
		maxim = i;
		for(j  = i - 1; j >= 0; j--)
			if(v[j] < v[i] && nr[maxim] <= nr[j])
				maxim = j;

		if(maxim != i){
			nr[i] += nr[maxim];
			copy(&L[maxim], &L[i]);
		}
	}

	maxim = n - 1;
	for(i = n - 1; i > 0; i--)
		if(nr[i] > nr[maxim])
			maxim = i;

	printf("%d\n", nr[maxim]);
	AfiL(L[maxim]);
	printf("\n");

	return 0;
}

int ins(ALista L, int x){
	TLista aux = (TLista)malloc(sizeof(TCel));
	if(!aux) return 0;
	aux->urm = *L;
	aux->info = x;
	*L = aux;
}

int copy(ALista Ls, ALista Ld){
	if(!(*Ls)) return 1;
	copy(&(*Ls)->urm, Ld);
	TLista aux = (TLista)malloc(sizeof(TCel));
	if(!aux) return 0;
	aux->urm = *Ld;
	aux->info = (*Ls)->info;
	*Ld = aux;
}

void AfiL(TLista L){
	if(!L) return;
	printf("%d ", L->info);
	AfiL(L->urm);
}