Cod sursa(job #485362)

Utilizator akaSoarePoepscu Bogdan Ionut akaSoare Data 18 septembrie 2010 10:38:05
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>

using namespace std;

int n,s[100000],l[100000],p[100000];
void max2(int i)
{   int max1=0;
    for(int j=i+1;j<n;j++)
        if(l[j]>max1&&s[j]>s[i])
            max1=l[j],p[i]=j;
    if( max1==0)
        p[i]=-1;
    l[i]=max1+1;
}
void cauta()
{int max1=0,x,poz;
    for(int i=0;i<n;i++)
        if(l[i]>max1) max1=l[i],x=i;
    printf("%d\n",max1);
    poz=p[x];
    while(poz!=-1)
    {   printf("%d ",s[x]);
        x=poz;
        poz=p[x];
    }
    printf("%d", s[x]);


}
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d/n",&n);
    for(int i=0;i<n;i++)
        scanf("%d ",&s[i]);
    l[n-1]=1;
    p[n-1]=-1;
    for(int i=n-2; i>=0;i--)
        max2(i);
    cauta();
    int q;
    return 0;
}