Cod sursa(job #2105579)

Utilizator robertrRotaru Stefan Robert robertr Data 13 ianuarie 2018 17:40:46
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int i,j,n,lis[1001],next[1001],v[1001],sol[1001];
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    for(i=n;i>=1;i--)
    {
        next[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,next[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=next[p];
    }
    g<<ma<<'\n';
    for(i=1;i<=ma;i++)
        g<<sol[i]<<" ";
    return 0;
}