Cod sursa(job #1110450)

Utilizator AndreilAndrei Lecu Andreil Data 18 februarie 2014 08:29:45
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>
using namespace std;
int x[100001],n,l[100001],t[100001],Max,poz;
void cit()
{
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++)
    scanf("%d ",&x[i]);
}
void solve()
{
    int i,j,max;
    for(i=n;i>=1;i--)
    {
        max=-1;
        for(j=i;j<=n;j++)
        if(l[j]>max&&x[j]>x[i])
        {
            max=l[j];
            t[i]=j;
        }
        l[i]=max+1;
        if(Max<l[i])
        {
            Max=l[i];
            poz=i;
        }
    }
}
void afis()
{
    int i=poz;
    printf("%d ",x[poz]);
    while(t[i]&&t[i]!=i)
    {printf("%d ",x[t[i]]);
    i=t[i];
    }
}
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    cit();
    solve();
    printf("%d\n",Max+1);
    afis();
    return 0;
}