Cod sursa(job #2133669)

Utilizator razvanradulescuRadulescu Razvan razvanradulescu Data 17 februarie 2018 10:52:20
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <cstdio>
using namespace std;

int n, maxim = 1, poz = n-1;
long long a[100050];
int dp[100050];

void rez()
{
    scanf("%d\n", &n);
    for(int i = 0; i<n; i++)
    {
        scanf("%d ", &a[i]);
    }
    dp[n-1] = 1;
    int ma;
    for(int i = n-2; i>=0; i--)
    {
        ma = 0;
        for(int j = i+1; j<n; j++)
        {
            if(a[j]>a[i])
                ma = max(ma, dp[j]);
        }
        dp[i] = 1+ma;
        if(maxim<=dp[i])
        {
            poz = i;
            maxim = dp[i];
        }
    }
    int x = maxim-1;
    printf("%d\n%d ", maxim, a[poz]);
    for(int i = poz+1;x>0; i++)
    {
        if(a[i]>a[poz])
        {
            x--;
            poz = i;
            printf("%d ", a[poz]);
        }
    }
}

int main()
{
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);
    rez();
    return 0;
}