Cod sursa(job #2610949)

Utilizator andreihaivas006Daniel Haivas andreihaivas006 Data 5 mai 2020 22:09:44
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

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

int dp[100005], a[100005], n;

int main()
{
    int ansmx = 1;
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
    dp[1] = 1;
    int mx = 0;
    for (int i = 2; i <= n; i++)
    {
        for (int j = i - 1; j >= 1; j--)
            if (a[j] < a[i] && mx < dp[j])
                mx = dp[j];
        dp[i] = 1 + mx;
        ansmx = max(ansmx, dp[i]);
    }
    vector < int > ans(n + 1);
    fout << ansmx << "\n";
    int last = 1e9;
    for (int i = n; i >= 1; --i)
        if (dp[i] == ansmx && last > a[i])
        {
            ans.push_back(a[i]);
            last = a[i];
            --ansmx;
        }
    reverse(ans.begin(), ans.end());
    for (auto& it : ans)
    {
        if (!it)
            break;
        fout << it << " ";
    }
    fout << "\n";
    fin.close();
    fout.close();
    return 0;
}