arrays – Find the maximum increasing subsequence

Question:

There is a problem: You are given a sequence of integers. Find its maximum increasing subsequence. I found a solution on the Internet, but I just can't get it (+ 1,000,000 karma to someone who can explain to me how this program works

#include <vector>
using namespace std;

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
template<typename T> vector<int> find_lis(vector<T> &a)
{
    vector<int> b, p(a.size());
    int u, v;

    if (a.size() < 1) return b;

    b.push_back(0);

    for (int i = 1; i < (int)a.size(); i++) {
        if (a[b.back()] < a[i]) {
            p[i] = b.back();
            b.push_back(i);
            continue;
        }

        for (u = 0, v = b.size()-1; u < v;) {
            int c = (u + v) / 2;
            if (a[b[c]] < a[i]) u=c+1; else v=c;
        }

        if (a[i] < a[b[u]]) {
            if (u > 0) p[i] = b[u-1];
            b[u] = i;
        }  
    }

    for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
    return b;
}

/* Example of usage: */
#include <cstdio>
#include <conio.h>
int main()
{
    int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
    vector<int> seq(a, a+sizeof(a)/sizeof(a[0]));
    vector<int> lis = find_lis(seq);

    for (unsigned i = 0; i < lis.size(); i++)
        printf(i+1 < lis.size() ? "%d " : "%d\n", seq[lis[i]]);
 getch();
    return 0;
}

Answer:

See, it's not all that difficult.

The code is well written in terms of implementation details, but of course the names of the variables and their reuse with a different meaning does not add clarity to the algorithm.

I renamed the variables, separated them where necessary and provided them with comments.

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
template<typename T> vector<int> find_lis(vector<T> &data)
{
    // решаем задачу итеративно. сначала рассматриваем только первый элемент
    // затем добавляем элементы по одному

    // (бывший массив p)
    // вот это интересная штука. тут для каждого индекса i мы рассматриваем
    // наилучшую из подпоследовательностей, заканчивающихся **на этом элементе**,
    // и записываем в этот массив индекс предыдущего элемента.
    // мы пользуемся таким важным свойством: для наилучшей подпоследовательности,
    // заканчивающейся на i-ом элементе, её кусок без финального элемента обязан быть
    // наилучшей подпоследовательностью, заканчивающейся на соответствующем
    // элементе. поэтому для хранения наилучших подпоследовательностей достаточно
    // лишь одного предыдущего индекса
    vector<int> previdx(data.size());

    // бывший массив b
    // а здесь мы храним индексы тех элементов, которые **в принципе** могут стать
    // чьим-то предыдущим элементом в наилучшей последовательности.
    // список хранится в таком порядке, чтобы соответствующие данные
    // были отсортированы (чтобы можно было искать двоичным поиском)
    vector<int> possibleprev;

    // тривиальный случай
    if (data.size() < 1) return vector<int>();

    possibleprev.push_back(0); // для одного элемента всё просто

    for (int i = 1; i < (int)data.size(); i++) {
        // вводим в рассмотрение следующий элемент и обновляем списки

        T curr = data[i];

        // если новый элемент больше всех возможных предыдущих элементов...
        if (data[possibleprev.back()] < curr) {
            // ... то всё просто: его предыдущий элемент - наибольший из возможных
            previdx[i] = possibleprev.back();
            // и он сам - тоже возможный наибольший для кого-то после
            possibleprev.push_back(i);
            continue; // всё, переходим к следующему элементу
        }

        // теперь более интересный случай: мы попали в середину

        int leftidx, rightidx;

        // старый знакомый -- поиск половинным делением.
        // ищем в упорядоченном списке предыдущих элементов,
        // куда можно вставить новый элемент
        for (leftidx = 0, rightidx = possibleprev.size()-1; leftidx < rightidx;) {
            int mididx = (leftidx + rightidx) / 2;
            if (data[possibleprev[mididx]] < curr)
                leftidx=mididx+1;
            else
                rightidx=mididx;
        }
        int foundidx = leftidx;

        if (curr < data[possibleprev[foundidx]]) {
            // нашли наш предыдущий индекс!
            // записываем найденное значение в таблицу previdx:
            if (foundidx > 0) previdx[i] = possibleprev[foundidx-1];
            // и корректируем текущий список possibleprev
            // ключевой момент - теперь найденный элемент в таблице possibleprev
            // индекс больше не нужен
            possibleprev[foundidx] = i;
        }
    }

    // отлично, собираем ответ. это будет последовательность индексов,
    // "связанная" через previdx
    vector<int> bestsubseq(possibleprev.size());
    // клёвый трюк с индексами, не знал раньше.
    // обратите внимание, начальное значение seqindex будет bestsubseq.size() - 1
    for (int seqindex = bestsubseq.size(), dataindex = possibleprev.back();
         seqindex-- != 0;
         dataindex = previdx[dataindex])
        bestsubseq[seqindex] = dataindex;
    return bestsubseq;
}

Everything!