Cod sursa(job #1557270)

Utilizator tc_iuresiures tudor-cristian tc_iures Data 27 decembrie 2015 08:44:09
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 100005;

int N, v[Nmax];
int best[Nmax], succ[Nmax], Max = -1, iMax;

void read()
{
    ifstream f("scmax.in");
    f >> N;
    for(int i = 1; i <= N; i ++)
    {
        f >> v[i];
    }
    f.close();
}

void solve()
{
    best[N] = 1;
    succ[N] = 0;
    for(int i = N-1; i >= 1; i --)
    {
        best[i] = 1;
        succ[i] = 0;
        for(int j = i+1; j <= N; j ++)
        {
            if((best[i] <= best[j]) && (v[i]<v[j]))
            {
                best[i] = best[j] + 1;
                succ[i] = j;
                if(best[i] > Max)
                {
                    Max = best[i];
                    iMax = i;
                }
            }
        }
    }

}

void print()
{
    ofstream g("scmax.out");
    g << Max << "\n";
    while(iMax != 0)
    {
        g << v[iMax] << " ";
        iMax = succ[iMax];
    }
    g.close();
}

int main()
{
    read();
    solve();
    print();
    return 0;
}