Cod sursa(job #1189362)

Utilizator GabyGabyGabriel Tuculina GabyGaby Data 22 mai 2014 16:14:56
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n, i, j, k, v[100001], d[100001], t[100001], w[100001], maxim, poz;

int main(){
    fin>>n;
    for(i=1;i<=n; i++)
        fin>>v[i];
    d[1]=1;
    for(i=2; i<=n; i++){
        maxim=0;
        for(j=1; j<i; j++){
            if(d[j]>maxim && v[i]>v[j]) {
                maxim=d[j];
                poz=j;
            }
        }
        d[i]=maxim+1;
        if(d[i]!=1)
            t[i]=poz;
    }

    maxim=0;
    for(i=1; i<=n; i++)
        if(maxim<d[i]){
            maxim=d[i];
            poz=i;
        }
    fout<<maxim<<"\n";
    while(poz!=0){
        w[++k]=v[poz];
        poz=t[poz];
    }
    for(i=k; i>=1; i--)
        fout<<w[i]<<" ";
    return 0;
}