Cod sursa(job #2240890)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 14 septembrie 2018 12:56:11
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, v[100005], best[100005], pre[100005], i, j, mx;
void sir(int i)
{
    if (pre[i] != 0) sir(pre[i]);
    fout << v[i] << " ";
}
int main()
{
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> v[i];
    best[1] = 1;
    for (i = 2; i <= n; i++)
    {
        best[i] = 1;
        for (j = 1; j < i; j++)
            if (v[i] > v[j] && best[j] + 1 > best[i])
            {
                best[i] = best[j] + 1;
                pre[i] = j;
            }
    }
    for (i = 1; i <= n; i++)
        if (best[i] > best[mx]) mx = i;
    fout << best[mx] << "\n";
    sir(mx);
    return 0;
}