Cod sursa(job #1898932)

Utilizator andreinmAndrei andreinm Data 2 martie 2017 13:29:44
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>

using namespace std;

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

const int NM = 110;
const int inf = 2e9 + 10;

int N, i;
int v[NM], best[NM], prv[NM];

int get_pos(int n) {
    int res = 0;

    int left = 1; int right = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (v[best[mid]] < v[n])
            res = mid, left = mid + 1;
        else right = mid - 1;
    }

    return res;
}

void print_lis(int n) {
    if (n == 0) return;

    print_lis(prv[n]);
    out << v[n] << ' ';
}

int main()
{
    in >> N;
    for (i = 1; i <= N; ++i) {
        in >> v[i];
    }

    v[0] = inf;
    for (i = 1; i <= N; ++i) {
        int current = get_pos(i);

        best[current + 1] = i;
        prv[i] = best[current];
    }

    int ans;
    for (ans = 1; best[ans+1]; ++ans);

    out << ans << '\n';
    print_lis(best[ans]);

    return 0;
}