Cod sursa(job #2454093)

Utilizator pregoliStana Andrei pregoli Data 7 septembrie 2019 13:56:37
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;

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

#define NMAX 100005
int v[NMAX], n, maxi, dp[NMAX], poz[NMAX], poz2;

void Read()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
}

void display(int p)
{
    if (!p)
        return;
    display(poz[p]);
    fout << v[p] << ' ';
}

int main()
{
    Read();
    for (int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        for (int j = i - 1; j; j--)
            if (v[j] < v[i])
            {
                if (dp[i] < dp[j] + 1)
                    {
                        dp[i] = dp[j] + 1;
                        poz[i] = j;
                    }
            }
    }
    for (int i = 1; i <= n; i++)
    {
        if (dp[i] > maxi)
        {
            maxi = dp[i];
            poz2 = i;
        }
    }
    fout << maxi << '\n';
    display(poz2);
    return EXIT_SUCCESS;
}