Cod sursa(job #2687396)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 19 decembrie 2020 23:25:05
Problema Subsir crescator maximal Scor 70
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#define MAX_N 100000
int v[MAX_N], len[MAX_N], prev[MAX_N], rasp[MAX_N];
int main() {
    FILE *fin, *fout;
    int n, maxLen, m, p, i, j;
    fin = fopen( "scmax.in", "r" );
    fscanf( fin, "%d", &n );
    maxLen = 0;
    p = -1;
    for ( i = 0; i < n; i++ ) {
        fscanf( fin, "%d", &v[i] );
        len[i] = 1;
        prev[i] = -1;
        for ( j = 0; j < i; j++ ) {
            if ( v[j] < v[i] ) {
                if ( len[j] + 1 > len[i] ) {
                    len[i] = len[j] + 1;
                    prev[i] = j;
                }
            }
        }
        if ( len[i] > maxLen ) {
            maxLen = len[i];
            p = i;
        }
    }
    fclose( fin );
    fout = fopen( "scmax.out", "w" );
    fprintf( fout, "%d\n", maxLen );
    m = 0;
    while ( p != -1 ) {
        rasp[m] = v[p];
        m++;
        printf( "%d ", p );
        p = prev[p];
    }
    for ( i = m - 1; i >= 0; i-- )
        fprintf( fout, "%d ", rasp[i] );
    fclose( fout );
    return 0;
}