LIS PROPIA

#include <iostream>
#include <algorithm>
#include <vector>

#define numero_actual v[i]

using namespace std;

vector<int> LIS (const int &n, const vector<int> &v)
{
    vector < vector<int> > r (n+1);

    int lis = 1;

    r[1].push_back( v[0] );///meto el primer elemento

    for (int i=1; i<n; i++) /// recorre todos los numeros
        for (int j=lis; j>=1; j--) /// recorro cada mejor LIS guardada al reves
            if ( numero_actual > r[j].back() ) /// si puede poner el numero al final de esta lista...
                if ( !r[j+1].size() || numero_actual < r[j+1].back() ) ///y mientras sea mejor añadirla...
                {
                    lis = max(lis, j+1);

                    r[j+1] = r[j];
                    r[j+1].push_back( numero_actual ); ///la añade;
                }

    return r[lis];
}

int main()
{
    int n;
    cin>>n;

    vector <int> v (n);
    for (int i=0; i<n; i++)
        cin>>v[i];

    for (int i=0; i<n; i++)
        cout<<v[i]<<" ";
     cout<<endl;

    vector<int> r = LIS(n, v);

    for (int i=0; i<r.size(); i++)
        cout<<r[i]<<" ";

    return 0;
}

/*  8
    1 7 2 11 15 4 21 9  */