Cod sursa(job #908861)

Utilizator sandugavrilaGavrila Alexandru sandugavrila Data 10 martie 2013 09:07:46
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <stdio.h>

using namespace std;
int v[100005],l[100005];
int main()
{
    int n,i,j,mx,lmax=1,poz,lim;
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);

    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    l[n]=1;
    for(i=n-1;i>=1;i--)
    {
        mx=0;
        for(j=i+1;j<=n;j++)
            if(v[j]>v[i]&&l[j]>mx)
                mx=l[j];
        l[i]=mx+1;
        if(l[i]>lmax)
        {
            lmax=l[i];
            poz=i;
        }
    }
    printf("%d\n",lmax);
    lim=v[poz];
    printf("%d ",lim);
    for(i=poz+1;i<=n;i++)
    {
        if(v[i]>=lim&&l[i]==lmax-1)
        {
            printf("%d ",v[i]);
            lmax--;
        }

    }



    return 0;
}