Cod sursa(job #2694325)

Utilizator andrei_ciobanuciobanu andrei andrei_ciobanu Data 8 ianuarie 2021 19:55:41
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <cstdio>
using namespace std;

#define MAXN 100000

int precedentIndex[MAXN]={-1}, maxLengthI[MAXN], arr[MAXN];

FILE *fout;

void print_path(int index){
    if (index<0) return;
    int precedent=precedentIndex[index];
    print_path(precedent);
    fprintf(fout, "%d ", arr[index]);
}

int main()
{
    FILE *fin=fopen("scmax.in", "r");
    int N;
    fscanf(fin, "%d", &N);

    for (int i=0; i<N; i++) fscanf(fin, "%d", &arr[i]);
    fclose(fin);

    int maxLength=-1, lastIndex;
    for (int i=0; i<N; i++){
        maxLengthI[i]=1;
        precedentIndex[i]=-1;
        for (int j=i-1; j>=0; j--){
            if (arr[j]<arr[i] && maxLengthI[j]+1>maxLengthI[i]){
                maxLengthI[i]=1+maxLengthI[j];
                precedentIndex[i]=j;
            }
        }
        if (maxLengthI[i]>maxLength){
            maxLength=maxLengthI[i];
            lastIndex=i;
        }
    }

    fout=fopen("scmax.out", "w");
    fprintf(fout, "%d\n", maxLength);
    print_path(lastIndex);
    fclose(fout);
    return 0;
}