Cod sursa(job #1853308)

Utilizator TimoteiCopaciu Timotei Timotei Data 21 ianuarie 2017 16:54:46
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>

using namespace std;
int n, v[100005], best[100005], maxL, poz_maxL, poz[100005];
void read()
{
    ifstream fin("scmax.in");
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> v[i];
}
int max_best(int x)
{
    int mx = -1;
    for(int i = x + 1; i <= n; ++i)
        if(v[i] > v[x] && best[i] > mx){
            mx = best[i];
            poz[x] = i;
        }

    return mx;
}
void solve()
{
    best[n] = 1;
    poz[n] = -1;
    for(int i = n - 1; i >= 1; --i){
        best[i] = max_best(i) + 1;
        if(best[i] > maxL){
            maxL = best[i];
            poz_maxL = i;
        }
    }
}
void write()
{
    ofstream fout("scmax.out");
    fout << maxL << '\n';
    for(int i = 1; i <= maxL; ++i){
        fout << v[poz_maxL] << ' ';
        poz_maxL = poz[poz_maxL];
    }
}
int main()
{
    read();
    solve();
    write();
    return 0;
}