Cod sursa(job #2496850)

Utilizator andreicadarCadar Andrei andreicadar Data 21 noiembrie 2019 19:07:18
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

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

int v[100001],n,dp[100001];

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

void Solve()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        dp[i] = 1;
        for(j=1;j<=i;j++)
            if(v[j]<v[i])
                {
                    if(dp[j]+1 > dp[i])
                    dp[i] = dp[j]+1;
                }

    }
    int mx = 0;
    int poz_sol=1;
    vector <int> sol;
    for(i=1;i<=n;i++)
        {
            if(mx<dp[i])
                mx = dp[i];

        }

    for(i=n;i>=1;i--)
        if(dp[i]==mx)
    {
        sol.push_back(v[i]);

        mx--;
    }

    g<<sol.size()<<endl;


    for(i=sol.size()-1;i>=0;i--)
        g<<sol[i]<<" ";


}

int main()
{
    Read();
    Solve();
}