Cod sursa(job #1781625)

Utilizator anamaria41Raicu Ana anamaria41 Data 17 octombrie 2016 09:26:29
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>

using namespace std;
int n,M,i,v[100050],l[100050],maxi,p,j;
int main()
{
    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;M=0;

    for(i=n-1; i>=1; i--)
    {
        maxi=0;
        for(j=i+1; j<=n; j++)
            if(v[i]<v[j] && l[j]>maxi)
            {
                maxi=l[j];
                l[i]=maxi+1;
            }
        if(l[i]>M)
        {
            M=l[i];
            p=i;
        }
    }

    printf("%d\n",M);
    printf("%d ",v[p]);

    M--;

    for(i=p+1; i<=n; i++)
        if(v[i]>v[p] && l[i]==M)
        {
            printf("%d ",v[i]);
            p=i;
            M--;
        }

    return 0;
}