Cod sursa(job #1293797)

Utilizator mmc170597Marin Mihnea Cristian mmc170597 Data 16 decembrie 2014 16:28:13
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>
using namespace std;
int v[100001],n,l[100001],u[100001];
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    int i,j,m,poz;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&v[i]);
    }
    //urmeaza dinamica
    l[n]=1;
    for(i=n-1;i>=1;i--){
        m=0;
        for(j=i+1;j<=n;j++){
            if(v[j]>v[i])
            if(l[j]>m){
                m=l[j];
                poz=j;
            }
        }
        l[i]=m+1;
        u[i]=poz;
    }
    m=l[1];
    poz=1;
    for(i=2;i<=n;i++)
    if(l[i]>m){
        m=l[i];
        poz=i;
    }
    printf("%d\n",m);
    int cnt=m;
    while(m){
        printf("%d ",v[poz]);
        poz=u[poz];
        m--;
    }
    return 0;
}