Cod sursa(job #2386175)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 22 martie 2019 12:29:33
Problema Subsir crescator maximal Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
using namespace std;
int n,V[200001],P,i,j,maxim,D[200001],T[200001],u,k,SOL[200001];
int main()
{
    ifstream fin ("scmax.in");
    ofstream fout("scmax.out");
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>V[i];
    D[1]=1;
    V[++n]=1000000000;
    for(i=2;i<=n;i++)
    {
        maxim=0;
        P=0;
        for(j=1;j<i;j++)
        {
            if(V[j]<V[i]&&D[j]>maxim)
            {
                maxim=D[j];
                P=j;
            }
        }
        D[i]=maxim+1;
        T[i]=P;
    }
    fout<<D[n]-1<<"\n";
    u=T[n];
    while(u!=0)
    {
        SOL[++k]=V[u];
        u=T[u];
    }
    for(i=k;i>=1;i--)
        fout<<SOL[i]<<" ";
    return 0;
}