ex18

#include <stdio.h>
#include <stdlib.h>
int v[100005], maxim[100005];

void  lungMax(int n) { // am cautat pe net despre programarea dimanica
	int i, j, valMax;
	maxim[n - 1] = 1;
	for (i = n - 2; i >= 0; i--) {  // complexitate O(n^2 /2) -> limita de timp 5s
		maxim[i] = 1;
		for (j = i + 1; j < n; j++) {
			if (v[i] <= v[j] && maxim[i] <= maxim[j])
				maxim[i] = maxim[j] + 1;
		}
	}
	valMax = maxim[n - 1];
	for (i = n - 2; i; i--) // elementele mereu trebuie sa fie valoarea maxima pana la pozitia curenta
		if (maxim[i] < valMax)
		maxim[i] = valMax;
		else
			valMax = maxim[i];
}

int main() {

	int l, n = 0, k;
	FILE *f, *g;
	char s[2];
	f = fopen("in.txt", "r");// deschidere in mod citire
	while (fscanf(f, "%d%[\n]s", &v[n++], &s) == 1);// niste batai de cap am avut totusi cu fscanf

	fscanf(f, "%d", &l);
	lungMax(n);
	g = fopen("out.txt", "w");
	while (l) {
		fscanf(f, "%d", &k);
		fprintf(g, "%d\n", maxim[k + 1]); // acum in maxim se afla pentru fiecare din index din sir
		l--;                             // subsirul maxim asa ca e destul de rapid algoritmul
	}
	fclose(f);
	fclose(g);
	return 0;
}