Cod sursa(job #1020431)

Utilizator dan.lincanDan Lincan dan.lincan Data 2 noiembrie 2013 01:40:47
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>

using namespace std;

int n;
vector<int> a;
vector<int> best;
vector<int> pre;

int longest_length = 1;
int longest_start_position = -1;

ifstream in ("scmax.in" );
ofstream out("scmax.out");

template<class T>
void pv(vector<T> &a)
{
    for(const auto &v : a) cout << setw(3) << v << " ";
    cout << endl;
}

void print_numbers_reverse(int i)
{
    if(i == -1) return;
    print_numbers_reverse(pre[i]);
    out << a[i] << " ";
}

void read()
{
    in >> n;
    a.resize(n);
    for(int i = 0; i < n; ++i)
        in >> a[i];
}

void solve()
{
    best.resize(n, 1);
    pre.resize(n, -1);

    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < i; ++j)
        {
            if(a[j] < a[i] && best[i] < best[j] + 1)
            {
                best[i] = best[j] + 1;
                if( longest_length < best[i] )
                {
                    longest_length = best[i];
                    longest_start_position = i;
                }
                pre[i] = j;
            }
        }
    }
}

void print_solution()
{
    out << longest_length << "\n";
    print_numbers_reverse(longest_start_position);
}

int main()
{
    read();
    solve();
    print_solution();

    return 0;
}