Cod sursa(job #2023147)

Utilizator rangal3Tudor Anastasiei rangal3 Data 18 septembrie 2017 12:46:50
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#define max(a,b) (a > b ? a:b)
#define in "scmax.in"
#define out "scmax.out"
#define N 100003

using namespace std;

ifstream fin(in);
ofstream fout(out);

int v[N],n;
int ant[N],best[N];
int Max = 1;


void PD()
{
    ant[1] = 0;
    best[1] = 1;

    int bestM,indexM;

    for(int i=2; i<=n; ++i)
    {
         bestM = -1;
         indexM = 0;
         for(int k=i-1; k>=0; --k)
            if(v[k] < v[i])
                if(bestM < best[k])
                 {
                     bestM = best[k] + 1;
                     ant[i] = k;
                 }
        best[i] = bestM;
        Max = max(Max,best[i]);
    }
}

inline void afisare(int k)
{
    if(k == 0) return;
    afisare(ant[k]);
    fout<<v[k]<<" ";
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; ++i)
        fin>>v[i];

    PD();

    bool gasit = false;

    fout<<Max<<"\n";

    for(int i = n; !gasit; --i)
        if(best[i] == Max)
        {
            gasit = true;
            afisare(i);
        }

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