Cod sursa(job #2304545)

Utilizator MihneaHedeaHedea Mihnea MihneaHedea Data 18 decembrie 2018 10:26:35
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#define DIM 100005

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n,a[DIM],i,L[DIM],maxim,j,poz,T[DIM];
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    L[n]=1;
    T[n]=-1;
    maxim=-1;
    poz=n;
    for(i=n-1;i>=1;--i){
        L[i]=1;
        T[i]=-1;
        for(j=i+1;j<=n;++j)
            if(a[i]<a[j] && L[i]<L[j]+1){
                L[i]=L[j]+1;
                T[i]=j;
                if(L[i]>maxim){
                    maxim=L[i];
                    poz=i;
                }

            }
    }
    fout<<maxim<<"\n";
    i=poz;
    while(i!=-1){
        fout<<a[i]<<" ";
        i=T[i];
    }
    return 0;
}