Cod sursa(job #1426769)

Utilizator CiobraNume Prenume Ciobra Data 30 aprilie 2015 17:04:05
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <vector>
#include <fstream>

#define  ll long long
using namespace std;

int dp[100000];

int main()
{
    ll n;
    vector <ll> v(n);
    int cnt = 0;
    ifstream f("scmax.in");
    ofstream g("scmax.out");

    f >> n;
    for (int i = 0; i < n; i++)
        f >> v[i];

    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            if (v[j] > v[i]) {
                dp[j] = dp[i] + 1;
                if (dp[j] > cnt)
                    cnt = dp[j];
            }
        }
    }
    g << cnt + 1 << endl;

    vector <int> result;
    for (int i = n; i >= 0; --i) {
        if (dp[i] == cnt) {
            result.push_back(v[i]);
            --cnt;
        }
    }

    for (int i = result.size() - 1; i >= 0; i--)
        g << result[i] << " ";

    f.close();
    g.close();
    return 0;
}