Cod sursa(job #1730716)

Utilizator RRomaniucRomaniuc Radu Andrei RRomaniuc Data 17 iulie 2016 15:17:25
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<stdio.h>
int v[100001], n, i, j, lmax[100001], pred[100001], lungimeMaxima, raspunsLungime = -1, raspunsPozitie, vafis[100001], k = 0;
int main()
{
    FILE *inputFile = fopen("scmax.in", "r"), *outputFile = fopen("scmax.out", "w");
    
    fscanf(inputFile, "%d", &n);
    
    for(i = 1; i <= n; i++)
        fscanf(inputFile, "%d", v+i);
    
    lmax[1] = 1; pred[1] = -1;
    for(i = 2; i <= n; i++)
    {
        lungimeMaxima = -1;
        for(j = 1; j < i; j++)
            if(lmax[j] > lungimeMaxima && v[j] < v[i])
            {
                lungimeMaxima = lmax[j];
                pred[i] = j;
                lmax[i] = lungimeMaxima + 1;
                if(lmax[i] > raspunsLungime)
                {
                    raspunsLungime = lmax[i];
                    raspunsPozitie = i;
                }
            }
        
        if(lungimeMaxima == -1)
        {
            lmax[i] = 1;
            pred[i] = -1;
        }
        
    }
    
    fprintf(outputFile, "%d\n", raspunsLungime);
    
    i = raspunsPozitie;
    
    while(pred[i] != -1)
    {
        vafis[++k] = v[i];
        i = pred[i];
    }
    
    vafis[++k] = v[i];
    
    for(i = k; i >= 1; i--)
        fprintf(outputFile, "%d ", vafis[i]);
    
    return 0;
}