Cod sursa(job #1111106)

Utilizator alevasluialeHuhurez Marius alevasluiale Data 18 februarie 2014 17:15:34
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
using namespace std;
int lis[100001]; int v[100001];int next[100001];
int n,i,j,k,max,z,y;
int lungime(int a)
{
    int i,max;
    if(a!=0)
    {
        if(v[a]>v[a+1])
        {
            lis[a]=1;
            next[a]=a;
            return lungime(a-1);
        }
    else if(v[a]<v[a+1])
    {
        max=0;
        for(i=a+1;i<=n;i++) if(lis[i]>max&&v[i]>v[a]) max=lis[i],j=i;
        lis[a]=1+max;
        next[a]=j;
        return lungime(a-1);
    }
    else return lungime(a-1);
    }
    else return 0;
}
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    lis[n]=1;
    next[n]=n;
    for(i=1;i<=n;i++) scanf("%d",&v[i]);
    lungime(n-1);
    max=0;
    for(i=1;i<=n;i++) if(lis[i]>max) max=lis[i],y=i;
    printf("%d\n",max);
    printf("%d ",v[y]);
    j=y;
    for(i=y;i>=1;i--)
    {
        printf("%d ",v[next[j]]);
        j=next[j];
        }
}