Cod sursa(job #2130070)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 13 februarie 2018 13:40:07
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

using namespace std;
ifstream f ("scmax.in");
ofstream g ("scmax.out");
int n,i,a[100002],l[100002],lMax,Max,j,poz,sol[100002],vf=0;
void afis (int k,int lMax)
{
    if (lMax==0) return ;
    else if (l[k]==lMax)
    {
        vf++;
        sol[vf]=a[k];
        afis(k-1,lMax-1);
    }
    else
    {
        afis(k-1,lMax);
    }
}
int main()
{
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>a[i];
    }
    l[1]=1;poz=1;lMax=1;
    for (i=2;i<=n;i++)
    {
        Max=0;
        for (j=1;j<=i-1;j++)
        {
            if (a[j]<a[i] && l[j]>Max) Max=l[j];
        }
        l[i]=Max+1;
        if (l[i]>lMax)
        {
            lMax=l[i];
            poz=i;
        }
    }
    g<<lMax<<'\n';
    afis(poz,lMax);
    for (i=vf;i>=1;i--) g<<sol[i]<<" ";
    return 0;
}