Cod sursa(job #202267)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 7 august 2008 09:14:52
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>

int main()
{
    FILE *in = fopen("scmax.in","r");
    int n;
    fscanf(in,"%d",&n);
    int A[n+1],i;
    for (i=1;i<=n;i++) fscanf(in,"%d",&A[i]);
    fclose(in);
    int j,L[n+1],P[n+1],max,pmax;
    L[n] = 1;
    P[n] =-1;
    max = 1;
    pmax = n;
    for (i=n-1;i>0;i--)
        for (j=i+1,L[i]=1,P[i]=-1;j<=n;j++)
        if (A[i]<A[j] && L[i]<L[j]+1) {
                                        L[i] = L[j]+1;
                                        P[i] = j;
                                        if (L[i]>max) {max = L[i]; pmax = i;}
                                      }
    FILE *out = fopen("scmax.out","w");
    fprintf(out,"%d\n",max);
    for (;pmax!=-1;pmax=P[pmax]) fprintf(out,"%d ",A[pmax]);
    fclose(out);
}