Cod sursa(job #1318325)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 15 ianuarie 2015 20:46:50
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#define NMax 100005
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int N,X[NMax],DP[NMax],Succ[NMax];

void Read()
{
    fin>>N;
    for(int i=1;i<=N;i++)
        fin>>X[i];
}

void Solve()
{

    for(int i=N;i>=1;i--)
        {
           DP[i] = 0;

           for(int j=i+1;j<=N;j++)
                if(X[j]>X[i] && DP[j]>DP[i])
                    {
                        DP[i] = DP[j];
                        Succ[i] = j;
                    }


           DP[i]++;

        }

}
void Print()
{
    int Sol = 0, PSol = 0;
    for(int i=1;i<=N;i++)
        {
            if(DP[i]>Sol)
                {
                    Sol=DP[i];
                    PSol = i;
                }

        }
    fout<<Sol<<"\n";
    int i = PSol;
    while(i)
        {
            fout<<X[i]<<" ";
            i = Succ[i];
        }
    fout<<"\n";
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}