Cod sursa(job #1473656)

Utilizator IoanaDanielaRomcea Ioana Daniela IoanaDaniela Data 19 august 2015 22:14:03
Problema Subsir crescator maximal Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 1.24 kb
#include <stdio.h>
#include <stdlib.h>


int get_index_best(int v[], int best[], int i){
    int max=0, poz=-1, j;
    for (j=0;j<i;j++){
        if ( (v[j]<v[i]) && (best[j]>max) )
        {
            max = best[j];
            poz = j ;
        }
    }
    return poz;
}


void afisare_subsir(int v[], int best[], int pre[], int i,FILE *g){
    int interm[100000],j=0;
    interm[0]=v[i];

    while(pre[i]!=-1){
        j++;
        i=pre[i];
        interm[j]=v[i];
    }

    int k;
    for (k=j;k>=0;k--)
        fprintf(g,"%d ",interm[k]);

}



int main()
{
    FILE *f,*g;
    int v[100000], best[100000], pre[100000];
    int imax=0, n,i;
    f = fopen("scmax.in","r");
    g = fopen("scmax.out","w");

    fscanf(f,"%d",&n);
    for(i=0; i<n; i++){
        fscanf(f,"%d",&v[i]);
        int interm = get_index_best(v,best,i);
        if (interm == -1){
            best[i] = 1;
            pre[i] = -1;
        }else{
            best[i] = best[interm] + 1;
            pre[i] = interm;
            if (best[i]>best[imax])
                imax = i;
        }
    }

    fprintf(g,"%d\n",best[imax]);
    afisare_subsir(v,best,pre,imax,g);


    fclose(f);
    fclose(g);
    return 0;
}