Cod sursa(job #2113082)

Utilizator infoinbloodIonut Bratu infoinblood Data 24 ianuarie 2018 11:09:58
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#define NMAX 100001

using namespace std;

int x[NMAX];
int dp[NMAX];
int aux[NMAX];

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

void afisare(int a)
{
    if(aux[a]!=-1)
    {
        afisare(aux[a]);
    }
    fout<<x[a]<<" ";
}

int main()
{
    int n;
    int i,j;
    fin>>n;
    for(i=1;i<=n;++i)
    {
        fin>>x[i];
        dp[i]=1;
        aux[i]=-1;
    }
    for(i=2;i<=n;++i)
    {
        for(j=1;j<i;++j)
        {
            if(x[i]>x[j])
            {
                if(dp[j]+1>dp[i])
                {
                    dp[i]=dp[j]+1;
                    aux[i]=j;                }
                }
        }
    }
    int maxim=0;
    int val=-1;
    for(i=1;i<=n;++i)
    {
        if(dp[i]>val)
        {
            maxim=i;
            val=dp[i];
        }
    }
    fout<<val;
    fout<<endl;
    afisare(maxim);
    return 0;
}