Cod sursa(job #3261820)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 7 decembrie 2024 12:49:05
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 1e5 + 1;
int N, ans, ansPos;
int v[N_MAX];
int dp[N_MAX], t[N_MAX];

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void ReadArray()
{
    cin >> N;

    for(int i = 1; i <= N; i++)
        cin >> v[i];
}

void DisplayPath(int p)
{
    if(t[p] != 0)
        DisplayPath(t[p]);
    cout << v[p] << ' ';
}

void Solve()
{
    dp[1] = 1;
    t[1] = 0;

    for(int i = 2, j, mx, p; i <= N; i++)
    {
        mx = 0;
        p = 0;

        for(j = 1; j < i; j++)
            if(v[j] < v[i] && dp[j] > mx)
            {
                mx = dp[j];
                p = j;
            }

        dp[i] = mx + 1;
        if(dp[i] == 1)
            t[i] = 0;
        else
            t[i] = p;

        if(dp[i] > ans)
        {
            ans = dp[i];
            ansPos = i;
        }
    }

    cout << ans << '\n';
    DisplayPath(ansPos);
}

int main()
{
    SetInput("scmax");

    ReadArray();
    Solve();

    return 0;
}