Cod sursa(job #1783535)

Utilizator netfreeAndrei Muntean netfree Data 19 octombrie 2016 08:54:20
Problema Subsir crescator maximal Scor 50
Compilator cpp Status done
Runda cerculdeinfo-lectia3-programaredinamica1 Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int x[100005],aux[100005],se_leaga_de[1000005],q[1000005];

int main()
{
    ifstream fin("scmax.in");
    ofstream fout("scmax.out");

    int i,n,j;

    fin>>n;
    for(i=1;i<=n;i++){
        fin>>x[i];
    }

    int sub_max, poz_sub_max,imaxx=0,poz_maxx=0;

    for(i=1;i<=n;i++){
        aux[i]=1;
        for(j=1;j<i;j++)
            if(x[i]>x[j] && aux[j]>=aux[i]){

                    aux[i]=aux[j]+1;
                    se_leaga_de[i]=j;
            }

        if(imaxx<aux[i]){
            imaxx=aux[i];
            poz_maxx=i;
        }

//        cout<<se_leaga_de[i]<<" ";
    }



    int new_i=0;

    q[++new_i]=x[poz_maxx];
    imaxx--;

    for(i=poz_maxx;i>=1;i--){
            if(aux[se_leaga_de[i]]==imaxx&&imaxx!=0){
                q[++new_i]=x[se_leaga_de[i]];
                imaxx--;
            }

    }

    reverse(q+1,q+new_i+1);

    fout<<new_i<<"\n";

    for(i=1;i<=new_i;i++)
        fout<<q[i]<<" ";



    fin.close();
    fout.close();
    return 0;
}