Cod sursa(job #2105582)

Utilizator robertrRotaru Stefan Robert robertr Data 13 ianuarie 2018 17:41:50
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int i,j,n,lis[100001],urm[100001],v[100001],sol[100001];
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    for(i=n;i>=1;i--)
    {
        urm[i]=-1;
        lis[i]=1;
        for(j=i+1;j<=n;j++)
        {
            if(v[j]>v[i])
               {if(lis[j]+1>lis[i])
                   lis[i]=lis[j]+1,urm[i]=j;}
        }
    }
    int p=0,ma=0;
    for(i=1;i<=n;i++)
        if(lis[i]>ma)
           ma=lis[i],p=i;
    int k=1;
    while(p!=-1)
    {
        sol[k++]=v[p];
        p=urm[p];
    }
    g<<ma<<'\n';
    for(i=1;i<=ma;i++)
        g<<sol[i]<<" ";
    return 0;
}