Cod sursa(job #3041591)

Utilizator VespaOlaru Amelia Vespa Data 31 martie 2023 19:09:30
Problema Subsir crescator maximal Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int dp[100005];
int main()
{
    int n,v[100005]={0};
    fin>>n;
    for(int i=0;i<n;i++)
    {
       fin>>v[i];

    }
    int pozmax=-1,maxi=-1;
    for(int i=n-1;i>=0;i--)
    {
        int nr=0;
        for(int j=i+1;j<n;j++)
        {
            if(v[i]<v[j])
            nr=max(nr,dp[j]);
        }
        dp[i]=nr+1;
        if(dp[i]>maxi)
        {
            maxi=dp[i];
            pozmax=i;
        }
    }
    //for(int i=0;i<n;i++)
       // cout<<dp[i]<<" ";
       // cout<<v[pozmax]<<" ";
    /*for(int i=pozmax+1;i<n;i++)
    {
        if(dp[i-1]==dp[i]+1)
            cout<<v[i];
    }*/
fout<<maxi<<'\n';
    int i=pozmax,lasti=i;maxi++;
    while(maxi!=0&&i<n)
    {
        if(dp[i]==maxi-1&&v[i]<v[lasti])///&&
        {
            maxi--;lasti=i;
           fout<<v[i]<<" ";
        }
        i++;
    }



    return 0;
}