Cod sursa(job #1874141)

Utilizator NicusorTelescu Nicolae Nicusor Data 9 februarie 2017 18:48:14
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <cstdio>

using namespace std;

int numere[100001],v[100001],val[100001],pred[100001];
int max_i,cnt;

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 ",&v[i]);
        for (int j=i-1;j>=1;--j)
            if (v[j]<v[i] && val[j]>val[i])
                val[i]=val[j], pred[i]=j;
        val[i]++;
        if (val[i]>val[max_i])
            max_i=i;
    }
    while(max_i)
    {
        numere[++cnt]=v[max_i];
        max_i=pred[max_i];
    }
    printf("%d\n",cnt);
    for (int i=cnt;i>=1;--i)
        printf("%d ",numere[i]);
}