Cod sursa(job #413101)

Utilizator eXtremeCornea Tudor eXtreme Data 7 martie 2010 17:39:59
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<stdio.h>

int pred[100001];
int best[100001];
int    v[100001];
int n;
int imax=-1;

void read(FILE *fin){
    int i;
    fscanf(fin, "%d", &n);
    for(i=0; i<n; ++i) fscanf(fin, "%d", &v[i]);
}    

void dinamic(){
    int i, j;       
    best[n-1]=1;  pred[n-1]=-1;
    for(i=n-2;i>=0;--i){
        best[i]=1; pred[i]=-1;
        for(j=i+1;j<n;++j)
          if(v[j]>v[i] && best[j]+1>best[i]){
              best[i]=best[j]+1;
              pred[i]=j;
              if(best[i]>best[imax]){
                  imax=i;
              }              
          }          
    }
}    

void sol(FILE * out){
    int i=imax;
    fprintf(out, "%d\n", best[i]);
    
    while(i!=-1){
        fprintf(out, "%d ", v[i]);
        i=pred[i];
    } 
}    

int main(){
    FILE * in=fopen("scmax.in", "r");
    FILE * out=fopen("scmax.out", "w");
    read(in); 
    dinamic();
    
    sol(out);
    fclose(out);
    
    return 0; 
}