Cod sursa(job #1603480)

Utilizator RaduToporanRadu Toporan RaduToporan Data 17 februarie 2016 16:34:37
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <cstdio>

int x[100005],lis[100005],n,i,j,MAX,maximul=-2000000000;

int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    for (i=1; i<=n; i++) scanf("%d",&x[i]);
    lis[n]=1;
    for (i=n-1; i>=1; i--)
    {
        MAX=0;
        for (j=i+1; j<=n; j++)
            if (MAX<lis[j] && x[i]<x[j]) MAX=lis[j];
        lis[i]=MAX+1;
    }
    for (i=1; i<=n; i++)
        if (lis[i]>maximul) maximul=lis[i];
    printf("%d\n",maximul);
    for (i=1; i<=n; i++)
        if (lis[i]==maximul)
    {
        printf("%d ",x[i]);
        maximul--;
    }
    printf("\n");
    return 0;
}