Cod sursa(job #2153518)

Utilizator ovantOvidiu Antal ovant Data 6 martie 2018 11:49:23
Problema Subsir crescator maximal Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>

using namespace std;

int n;
int a[10000];

void citire(){
    ifstream fin("scmax.in");
    fin>>n;
    for(int i=0;i<n;i++) fin>>a[i];
}

int best[10000], tata[100000];

void merg(){
    best[0]=1;
    tata[0]=-1;
    for(int i=1;i<n;i++){
        int m=0;
        best[i]=1;
        for(int j=0;j<i;j++){
            if(a[i]>a[j]&&best[j]>m){
                m=best[j];
                best[i]=best[j]+1;
                tata[i]=j;
            }
        }
        if(best[i]==1) tata[i]=-1;
    }
}

int v[10000],k;

void b(){
    ofstream fout("scmax.out");
    int m=0;
    for(int i=0;i<n;i++) if(best[i]>best[m]) m=i;
    fout<<best[m]<<"\n";
    int i=m;
    while(i>0){
        v[k++]=a[i];
        i=tata[i];
    }
    for(i=k-1;i>=0;i--) fout<<v[i]<<" ";
}

int main()
{
    citire();
    merg();
    b();
    return 0;
}