Cod sursa(job #1123093)

Utilizator SapientiaCHIRILA ADRIAN Sapientia Data 25 februarie 2014 22:35:35
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <cstdio>
#include <queue>
#define Nmax 100005
#define pp push_front
using namespace std;
int n;
int v[Nmax],u[Nmax];
deque <int> D;
void reading(int &n)
{
    int k;
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    for(k=1;k<=n;++k)
      scanf("%d",&v[k]);
}
void solve()
{
    int len=0,i,j,max,maxim=0,c;
    u[1]=1;
    for(i=2;i<=n;++i)
    {
        max=0;
        for(j=1;j<=i-1;++j)
        if (u[j]>max && v[i]>v[j]) max=u[j];
        u[i]=++max;
        if (max>maxim) {maxim=max;c=i;}
    }
    printf("%d\n",maxim);
    D.pp(v[c]);j=maxim;
    while(maxim)
    {
        --c;
        if (u[c]==maxim-1)
        {
            --maxim;
            D.pp(v[c]);
        }
    }
    for(i=1;i<=j;++i)
     printf("%d ",D[i]);
}
int main()
{
    reading(n);
    solve();
    return 0;
}