Cod sursa(job #485366)

Utilizator Viva12Ferentz Sergiu Viva12 Data 18 septembrie 2010 10:42:12
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>

using namespace std;
int a[100020],n,Lpoz[100020],Li[100020];
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    for (int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for (int i=0;i<n;i++)
    {
        Lpoz[i]=-1;
        Li[i]=1;
    }
    int lmax=0,llpoz;
    for (int i=n-2;i>=0;i--)
        {
            int j=i+1;
            while(j<n)
                {
                    if(a[i]<a[j])
                    {
                        Li[i]+=Li[j];
                        if(Li[i]>lmax)
                            {lmax=Li[i];
                            llpoz=j-1;
                            }
                        Lpoz[i]=j;
                    break;
                    }
                    j++;
                }
        }
        printf("%d\n",lmax);
        for (int i=0;i<lmax;i++)
            {
            printf("%d ",a[llpoz]);
            llpoz=Lpoz[llpoz];
            }





    return 0;
}