Cod sursa(job #1853312)

Utilizator TimoteiCopaciu Timotei Timotei Data 21 ianuarie 2017 17:07:31
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>

using namespace std;
int n, v[100005], best[100005], maxL = 1, poz_maxL, poz[100005];
void read()
{
    ifstream fin("scmax.in");
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> v[i];
}
void solve()
{
    best[n] = 1;
    poz[n] = -1;
    poz_maxL = n;
    for(int i = n - 1; i >= 1; --i){
     best[i] = 1;
      for(int j = i + 1; j <= n; ++j)
        if(v[i] < v[j] && best[j] + 1 > best[i]){
            best[i] = best[j] + 1;
            poz[i] = j;
        }
        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;
}