#include <stdio.h>
#include <malloc.h>
void citire(int* preturi[], int* scmax[], int* pozitii[], int *nr_luni,
int argc, char* argv[])
{
FILE *f;
//f = fopen(argv[1],"r");
f = fopen("scmax.in","r");
fscanf (f,"%d", nr_luni);
*preturi = (int*) malloc(*nr_luni * sizeof(int));
*scmax = (int*) malloc(*nr_luni * sizeof(int));
*pozitii = (int*) malloc(*nr_luni * sizeof(int));
for (int i = 0; i < *nr_luni; i++) {
fscanf (f,"%d", (*preturi)+i);
}
fclose(f);
}
int cautare_binara(int vector[], int dim, int val)
{
int st = 0, dr = dim - 1, mid;
while ( st <= dr) {
mid = (st + dr) / 2;
if (vector[mid] == val)
return mid;
if (vector[mid] > val)
dr = mid - 1;
else
st = mid + 1;
}
return st;
}
void construire_scmax(int scmax[], int pozitii[], int dim_scmax[],
int pret, int indice)
{
int poz = cautare_binara(scmax, *dim_scmax, pret);
scmax[poz] = pret;
pozitii[indice] = poz;
if (*dim_scmax <= poz)
(*dim_scmax)++;
}
void afisare_subsir_cresc(int pozitii[], int preturi[], int nr_luni, int lmax)
{
FILE *fisier;
int *solutie, dim = lmax + 1;
solutie = (int*) malloc((lmax + 1) * sizeof(int));
for (int i = nr_luni - 1; i >= 0 && lmax >= 0; i--) {
if (pozitii[i] == lmax) {
solutie[lmax] = preturi[i];
lmax--;
}
}
fisier = fopen("scmax.out","w");
fprintf (fisier,"%d\n", dim);
for (int i = 0; i < dim ; i++)
fprintf (fisier,"%d ", solutie[i]);
fprintf(fisier,"\n");
fclose(fisier);
free(solutie);
}
int main(int argc, char* argv[])
{
int nr_luni, poz_inserare, dim_scmax;
int *preturi,*scmax,*pozitii;
citire(&preturi,&scmax,&pozitii,&nr_luni, argc, argv);
dim_scmax = 0;
for (int i = 0 ; i < nr_luni; i++) {
construire_scmax(scmax, pozitii, &dim_scmax, preturi[i], i);
}
afisare_subsir_cresc(pozitii, preturi, nr_luni, dim_scmax - 1);
free (preturi);
free (scmax);
free (pozitii);
return 0;
}