Cod sursa(job #900842)

Utilizator RaduDoStochitoiu Radu RaduDo Data 28 februarie 2013 22:08:49
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<bitset>
#define INF 0x3f3f3f3f
#define mp make_pair
#define pb push_back
#define maxn 100010
using namespace std;
int L[maxn],poz[maxn],a[maxn],maxi,n,i,j,p;

int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; ++i)
        scanf("%d",&a[i]);

    L[n]=1; poz[n]=-1; maxi=1;
    for(i=n-1; i>0; --i)
    {
        L[i]=1; poz[i]=-1;
        for(j=i+1; j<=n; ++j)
            if(L[i]<=L[j] && a[i]<a[j])
            {
                L[i]=L[j]+1;
                poz[i]=j;
                if(L[i] > maxi)
                    maxi=L[i],p=i;
            }
    }
    printf("%d\n",maxi);
    while(p>0)
    {
        printf("%d ",a[p]);
        p=poz[p];
    }
    return 0;
}