Cod sursa(job #824094)

Utilizator mi5humihai draghici mi5hu Data 25 noiembrie 2012 20:54:29
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <stdio.h>
#define maxN 100100

int v[maxN];      // preturi
int lastEL[maxN]; // pretul ultimului produs din subsirul cu lung "i"
int pozV[maxN];   // pozitia in "v" a ultimului produs din subsirul cu lung "i"
int prev[maxN];   // prev[i] = pretul cadoului cumparat inaintea cadoului cu pretul "i"
int n;
int lastEL_AvailableP = 2;

int bsearch(int val, int st, int dr) {
		
	int m = (st + dr) / 2;
	if (st > dr) {
		return st;
	}
	if ((lastEL[m-1] < val) && (val <= lastEL[m]))
		return m;
	else if (val < lastEL[m]) { 
		return bsearch(val, st, m - 1);
	} else {
		return bsearch(val, m + 1, dr);
	}
}
void print(int poz) {
	if (poz == -1) {
		return;
	} else {
		print(prev[poz]);
		printf("%d ", v[poz]);
	}
}


int main(int argc, char** argv) {
	int poz;

	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	
	scanf("%d", &n);
	
	scanf("%d", &v[0]);
	lastEL[1] = v[0];
	pozV[1] = 0;
	prev[0] = -1;
	
	for (int i = 1; i < n; i++) {
		scanf("%d", &v[i]);
		
		//caut cel mai lung subsir ce are ultima valoare < v[i]
		poz = bsearch(v[i], 1, lastEL_AvailableP - 1);
		if (poz == -1) {
		} else if (poz >= lastEL_AvailableP) {
			lastEL[lastEL_AvailableP] = v[i];
			pozV[lastEL_AvailableP] = i;
			prev[i] = pozV[lastEL_AvailableP - 1];
			lastEL_AvailableP++;
		} else {
			lastEL[poz] = v[i];
			pozV[poz] = i;
			if (poz > 1) {
				prev[i] = pozV[poz - 1];
			} else {
				prev[i] = -1;
			}
		}	
	} 
	
	poz = lastEL_AvailableP - 1;
	printf("%d\n", lastEL_AvailableP - 1);
	print(pozV[poz]);
	
	return 0;
}