Cod sursa(job #1319908)

Utilizator lucaignatescuIgnatescu Luca lucaignatescu Data 17 ianuarie 2015 14:36:31
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
const int lg=100005;
using namespace std;
ifstream in("scmax.in");
ofstream out ("scmax.out");
int dp[lg], v[lg], pred[lg], sol[lg];
int n;
int main()
{
    int i, j;
    in>>n;
    dp[1]=1;
    pred[1] = 0;
    for(i=1; i<=n; ++i)
        in>>v[i];
    int poz, maxim;
    for(i=2; i<=n; ++i)
    {
        maxim = 0;
        poz = 0;
        for(j=1; j<i; ++j)
            if(v[j]<v[i] && dp[j] > maxim)
            {
                maxim = dp[j];
                poz = j;
            }
        dp[i] = maxim + 1;
        pred[i] = poz;
    }
    poz, maxim = 0;
    for (i = 1; i <= n; ++ i)
        if (dp[i] > maxim)
        {
            maxim = dp[i];
            poz = i;
        }
    out << maxim <<"\n";
    i = 1;
    while (poz != 0)
    {
        sol[i] = poz;
        poz = pred[poz];
        i++;
    }
    for (j = i - 1; j >= 1; -- j)
        out << v[sol[j]] << " " ;


    return 0;
}