Cod sursa(job #2005603)

Utilizator shantih1Alex S Hill shantih1 Data 27 iulie 2017 16:46:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
// facem varianta de 70 de pt cu programare dinamica.
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n, i, j, nr, v[100003], in, x, best[100003], pre[100003], mx;

deque <int> dq;

int main () {
    
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> v[i];
    
    best[1]=1;
    bool ok = 0;
    for (i = 2; i <= n; i++)
    {
        mx = 0;
        ok = 0;
        for (j = 1; j < i; j++)
            if (v[j] < v[i] && best[j] > mx)
            {
                mx = best[j];
                pre[i] = j;
                ok = 1;
            }
        if (ok == 1)    best[i] = mx + 1;
        else best[i] = 1;
    }
    
    /*for (i = 1; i <= n; i++)
        cout << best[i] << " ";
    cout << "\n";
    for (i = 1; i <= n; i++)
        cout << pre[i] << " ";*/
    
    mx = 0;
    for (i = 1; i <= n; i++)
        if (best[i] > mx)
        {   mx = best[i];   in = i;     }
    
    dq.push_back(v[in]);
    while (v[in] != 0)
    {
        in = pre[in];
        if (v[in] != 0)     dq.push_front(v[in]);
    }
    
    fout << mx << "\n";
    for (i = 0; i < dq.size(); i++)
        fout << dq[i] << " ";
}