Cod sursa(job #2165046)

Utilizator vasi461Vasiliu Dragos vasi461 Data 13 martie 2018 10:58:09
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
using namespace std;

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

#define MAX 100005

int n, a[MAX], dp[MAX], poz[MAX], c[MAX];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    for(int i = 1; i <= n; ++i)
    {
        dp[i] = 1;
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = i + 1; j <= n; ++j)
        {
            if(a[j] > a[i])
            {
                if(dp[j] < dp[i] + 1)
                {
                    dp[j] = dp[i] + 1;
                    poz[j] = i;
                }
            }
        }
    }
    int maxim = 0, p;
    for(int i = 1; i <= n; ++i)
    {
        if(dp[i] > maxim)
        {
            maxim = dp[i];
            p = i;
        }
    }
    cout << maxim << '\n';
    int i = p, k = 0;
    while(maxim > 0)
    {
        c[++k] = a[i];
        i = poz[i];
        maxim--;
    }
    for(int i = k; i >= 1; i--)
    {
        cout << c[i] << ' ';
    }
    cout << '\n';
    return 0;
}