Cod sursa(job #2321809)

Utilizator eugen_cuticCutic Eugen eugen_cutic Data 16 ianuarie 2019 17:37:57
Problema Subsir crescator maximal Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>

using namespace std;

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

void afis(int v[100001], int tata[200000], int index)
{
    if (tata[index] == -1)
        return;
    afis(v, tata, tata[index]);
    out << v[index] << " ";
}

int main()
{


    int n, v[100001];
    in >> n;
    for (int i = 0; i < n; i++)
        in >> v[i];

    int dp[100001], tata[200000], iFinal = 0;
    tata[0] = -1;
    dp[0] = 1;

    for (int i = 1; i < n; i++)
    {
        int lMax = -1;
        for (int j = 0; j < i; j++)
        {
            if (v[j] < v[i] && dp[j] > lMax)
            {
                lMax = dp[j];
                tata[i] = j;
                iFinal = i;
            }
        }
        dp[i] = lMax == -1 ? dp[i - 1] : max(dp[i - 1], 1 + lMax);
    }

    out << dp[n - 1] << endl;
    afis(v, tata, iFinal);

    return 0;
}