Cod sursa(job #1229239)

Utilizator thinkphpAdrian Statescu thinkphp Data 16 septembrie 2014 19:54:06
Problema Subsir crescator maximal Scor 15
Compilator c Status done
Runda Arhiva educationala Marime 1.39 kb
#include <stdio.h>
#define MAX 1000

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("scmax.in","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, maxBest = best[ 0 ], pos, k;

     fout = fopen("scmax.out","w");

     pos = 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 = 0; k < n; k++) {

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

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

              maxBest--;
           } 
     }

     fclose( fout );
   
};