Cod sursa(job #1523385)

Utilizator KOzarmOvidiu Badea KOzarm Data 12 noiembrie 2015 18:12:57
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>

using namespace std;
int v[100005],i,n,j,maxl,c,a[100005],k;
struct tle
{
    int x; int y;
}l[100005];
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    maxl=0;
    k=0;
    for(i=1;i<=n&&i+maxl<n;i++)
    {
        scanf("%d",&v[i]);
        for(j=0;j<i;j++)
        if(l[j].x+1>l[i].x&&v[j]<v[i])
        {
            l[i].x=l[j].x+1;
            l[i].y=j;
        }
        if(maxl<l[i].x)
        {
            maxl=l[i].x;
            k=i;
        }
    }
    j=k;
    a[1]=v[j];
    c=1;
    while(l[j].y!=0)
    {
        a[++c]=v[l[j].y];
        j=l[j].y;
    }
    printf("%d\n",c);
    for(i=c;i>0;i--)
        printf("%d ",a[i]);
    return 0;
}