Cod sursa(job #1229315)

Utilizator thinkphpAdrian Statescu thinkphp Data 16 septembrie 2014 21:49:33
Problema Subsir crescator maximal Scor 30
Compilator c Status done
Runda Arhiva educationala Marime 1.52 kb
#include <stdio.h>
#define MAX 1000
#define FIN "scmax.in"
#define FOUT "scmax.out"

FILE *fin, *fout;

void read();
void dynamicProgramming();
void write();

int vec[ MAX ], 
    n, 
    best[ MAX ];

int main() {
 
    read();

    dynamicProgramming();

    write();

    return 0;
}

void read() {

     int i;

     fin = fopen(FIN,"r");

     fscanf(fin, "%d", &n);

     for(i = 0; i < n; i++) {

         fscanf(fin, "%d", &vec[ i ]);
     } 

     fclose( fin );  
};

void dynamicProgramming() {

     int i,

         j, 

         max;

     best[ n - 1 ] = 1;

     for(i = n - 2; i >= 0; i--) {

         max = 0;

         for(j = i + 1; j < n; j++) {

                 if(vec[ i ] < vec[ j ] && best[ j ] > max) {

                       max = best[ j ];
                 }
         } 

         best[ i ] = 1 + max;  
     }
};

void write() {

  int i, 
      pos, 
      k,
      maxBest;

     fout = fopen(FOUT ,"w");

     pos = 0;

     maxBest = best[ 0 ];

     for(i = 1; i < n; i++) {

           if(best[i] > maxBest) { 

               maxBest = best[ i ];

               pos = i;
           }
     }  

     fprintf(fout, "%d\n", maxBest);   

     fprintf(fout, "%d ", vec[ pos ]);
   
     for(k = pos + 1; k < n; k++) {

           if(best[ k ] == maxBest - 1 && vec[ pos ] < vec[ k ]) {

              fprintf(fout, "%d ", vec[ k ]);

              maxBest--;
           } 
     }

     fclose( fout );
   
};