Cod sursa(job #1672490)

Utilizator robertdragomirescuRobert Dragomirescu robertdragomirescu Data 2 aprilie 2016 19:45:37
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cstdio>

using namespace std;
const int NMAX=100005;
int v[NMAX],b[NMAX],u[NMAX];
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    int n,i,j,mx=0,bm,p,nr;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    b[n]=1;
    for(i=n-1;i>=1;i--)
    {
        bm=0;
        for(j=i+1;j<=n;j++)
            if(v[j]>v[i]&&b[j]>bm)
            {
                bm=b[j];
                u[i]=j;
            }
        b[i]=bm+1;
        if(b[i]>mx)
        {
            mx=b[i];
            p=i;
        }
    }
    printf("%d\n",mx);
    for(i=1;i<=mx;i++)
    {
        printf("%d ",v[p]);
        p=u[p];
    }
    return 0;
}