Cod sursa(job #1868481)

Utilizator DragosArseneDragos Arsene DragosArsene Data 4 februarie 2017 23:09:57
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include<stdio.h>
using namespace std;
int v[100000], best[100000], q[100000];
int main() {
    FILE *fin, *fout;
    int a, b, x, y, n, maxx, i, maxim=1;

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

fscanf(fin,"%d", &n);
for(i=1;i<=n;i++){
    fscanf(fin,"%d", &v[i]);
}
maxx=0;
best[1]=1;
for(i=1;i<=n;i++){
    best[i]=1;
    maxx=-1;
    for(y=i;y>=1;y--){
        if(v[y]<v[i]&&best[y]>=maxx){
            best[i]=best[y]+1;
            maxx=best[i];
        }
        if(maxx>maxim)
            maxim=maxx;
    }
}
x=1;
a=maxim;
for(i=n;i>=1;i--){
    if(best[i]==maxim){
        q[x]=v[i];
        x++;
            maxim--;
    }

}
fprintf(fout,"%d\n", a);
for(i=x-1;i>=1;i--){
    fprintf(fout,"%d ", q[i]);
}
fclose(fin);
fclose(fout);
    return 0;
}