Cod sursa(job #1954122)

Utilizator papinub2Papa Valentin papinub2 Data 5 aprilie 2017 10:49:51
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n, maxim, p, nr, k;
int v[100010], best[100010], poz[100010];

int main()
{
    in >> n;

    for (int i = 1; i <= n; i++)
        in >> v[i];

        best[n] = 1;
        poz[n] = -1;
        p = n;

    for (int i = n - 1; i >= 1; i--)
    {
        best[i] = 1;
        poz[i] = -1;

        for (int j = i + 1; j <= n; j++)
        {
            if (v[i] < v[j] && best[i] < best[j] + 1)
            {
                best[i] = best[j] + 1;
                poz[i] = j;
                if (best[i] > maxim)
                {
                    maxim = best[i];
                    p = i;
                }
            }
        }
    }



    out << maxim << '\n';

    out << v[p] << ' ';

    while(poz[p] != -1)
    {
        nr++;

        k = poz[p];

        out << v[k] << ' ';

        p = k;
    }

    return 0;
}