Cod sursa(job #2705966)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 13 februarie 2021 16:31:24
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#define NMAX 100000
using namespace std;

int n;
int v[NMAX+3],dp[NMAX+3],prec[NMAX+3],sol[NMAX+3];

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

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
       fin>>v[i];
    }
    dp[1]=1;
    prec[1]=0;

    int maximDp=0,pozDp=0;
    for(int i=2; i<=n; i++)
    {
        int maxim=1,poz=0;
        for(int j=1; j<i; j++)
        {
            if(v[i]>v[j] && maxim<dp[j]+1)
            {
                maxim=dp[j]+1;
                poz=j;
            }
        }
        if(maximDp<maxim)
        {
            maximDp=maxim;
            pozDp=i;
        }
        dp[i]=maxim;
        prec[i]=poz;
    }

    int num=pozDp,elem=0;
    while(num>0)
    {
        sol[++elem]=v[num];
        num=prec[num];
    }
    fout<<maximDp<<endl;
    for(int i=elem; i>=1; i--)
    {
        fout<<sol[i]<<" ";
    }
    return 0;
}