Cod sursa(job #2741652)

Utilizator VladdStoicaStoica Vlad VladdStoica Data 17 aprilie 2021 10:23:45
Problema Subsir crescator maximal Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int n,v[100001],dp[100001],mx=0,currentX,fromX[100001],x,k=1,a[100001];
int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i];
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        for(int j=1;j<=i-1;j++)
        {
            if(v[j]<v[i])
            {
                dp[i]=1+dp[j];
                fromX[i]=j;
            }
        }
    }
    for(int i=1;i<=n;i++)
        if(dp[i]>mx)
        {
            mx=dp[i];
            currentX=i;
        }
    out<<mx<<"\n";
    while(currentX!=0)
    {
        x=currentX;
        a[k]=v[x];
        k++;
        currentX=fromX[x];
    }
    for(int i=k-1;i>=1;i--)
        out<<a[i]<<" ";
    return 0;
}