Cod sursa(job #2133707)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 17 februarie 2018 11:00:18
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>

using namespace std;
int n, a[100005], poz;
int dp[100005];

int main()
{

    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);

    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
    }
    dp[n]=1;
    for(int i=n-1; i>=1; i--)
    {
        int vmax=-1;
        for(int j=i+1; j<=n; j++)
        {
            if(a[j] > a[i] && 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  nrp=dp[poz];

    for(int i=poz+1; i<=n && nrp!=0; i++)
    {
        if(dp[i] == nrp-1)
        {
            printf("%d ", a[i]);
            nrp--;
        }
    }
    return 0;
}