Cod sursa(job #2109424)

Utilizator UWantMyNameGheorghe Vlad Camil UWantMyName Data 19 ianuarie 2018 18:35:08
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define in "scmax.in"
#define out "scmax.out"
#define nmax 100003
using namespace std;
ifstream fin(in);
ofstream fout(out);

int n;
int a[nmax];
int dp[nmax];
int urm[nmax];

void Read()
{
    int i;

    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
}

void Dyn()
{
    int i,j;
    int maxim,poz;

    dp[n] = 1;
    urm[n] = n+1;
    for (i = n-1; i >= 1; i--)
    {
        maxim = 0; poz = n+1;
        for (j = i+1; j <= n; j++)
            if (a[j] > a[i] && maxim < dp[j])
            {
                maxim = dp[j];
                poz = j;
            }
        dp[i] = 1 + maxim;
        urm[i] = poz;
    }

    poz = 1;
    for (i = 2; i <= n; i++)
        if (dp[i] > dp[poz]) poz = i;

    fout << dp[poz] << "\n";
    while (poz != n+1)
    {
        fout << a[poz] << " ";
        poz = urm[poz];
    }
}

int main()
{
    Read();
    Dyn();

    fin.close();
    fout.close();
    return 0;
}