Cod sursa(job #895468)

Utilizator dragosaioaneiAioanei Dragos dragosaioanei Data 27 februarie 2013 11:32:14
Problema Subsir crescator maximal Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
//Subsir Crescator Maximal
//Se da un vector a=(a1,a2,...,an)
//Subsir ai1, ai2, ai3, ... , aik
//Subsecventa ai+1, ai+2, ... , ai+k
//Sjubproblema Sa se determine cel mai lung subsir crescator care incepe la pozitia i
//lgmax[i]=lungimea celui mai lung subsir crescator care incepe la pozitia i
//urm[i]=pozitia elementului care urmeaza dupa a[i] in cel mai lung subsir crescator care incepe la pozitia i
//urm[i]=-1 daca nu exista urmator
//lgmax[i]=1+max{lgmax[j]}, j=i+1-->n, a[i]<=a[j]
//urm[i]=j maxim

#include<stdio.h>
#define IN "scmax.in"
#define OUT "scmax.out"
#define NMAX 101

int n,i,j,poz,maxim;
int a[NMAX];
int urmator[NMAX];
int lgmax[NMAX];

int main()
{
    FILE * fin=fopen(IN,"r");
    FILE * fout=fopen(OUT,"w");

    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(fin,"%d",&a[i]);
    for(i=n;i>=1;i--)
    {
        lgmax[i]=1;
        urmator[i]=-1;
        for(j=i+1;j<=n;j++)
        {
            if(a[j]>a[i] && lgmax[j]+1>lgmax[i])
            {
                lgmax[i]=lgmax[j]+1;
                urmator[i]=j;
            }
        }
    }
    maxim=0;
    for(i=1;i<=n;i++)
    {
        if(lgmax[i]>maxim)
        {
            maxim=lgmax[i];
            poz=i;
        }
    }
    fprintf(fout,"%d\n",lgmax[poz]);
    fprintf(fout,"%d",a[poz]);
    while(urmator[poz]!=-1 && urmator[poz]!=0)
    {
        fprintf(fout," %d",a[urmator[poz]]);
        poz=urmator[poz];
    }

    fclose(fin);
    fclose(fout);
    return 0;
}