Cod sursa(job #2133695)

Utilizator ana.pintiliciucAna Maria Pintiliciuc ana.pintiliciuc Data 17 februarie 2018 10:56:54
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>

using namespace std;

int a[100005], dp[100005];

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

        int vmax=0;
        for(int j=i+1;j<=n;j++)
        {
            if(a[j]>a[i])
                if(dp[j]>vmax)
                    vmax=dp[j];
        }
        dp[i]=1+vmax;
        if(dp[i]>dp[poz])
            poz=i;
    }
    printf("%d\n",dp[poz]);
    printf("%d ", a[poz]);
    int aux=dp[poz];
    for(int i=poz+1;i<=n;i++)
    {
            if(dp[i]==aux-1)
            {
                if(a[i]>a[poz])
                    printf("%d ", a[i]);
                aux--;
            }
    }


    return 0;
}