Найти максимальную возрастающую подпоследовательность

Есть задачка: Дана последовательность целых чисел. Найти ее максимальную возрастающую подпоследовательность. Нашла решение в интернете, но никак не могу вникнуть( +1000000 к карме тому, кто сможет мне объяснить принцип действия этой программы #include using namespace std;
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */ template vector find_lis(vector &a) { vector 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 #include int main() { int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }; vector seq(a, a+sizeof(a)/sizeof(a[0])); vector lis = find_lis(seq);
for (unsigned i = 0; i < lis.size(); i++) printf(i+1 < lis.size() ? "%d " : "%d
", seq[lis[i]]); getch(); return 0; }

Ответ

Смотрите, всё не так уж сложно. Код отлично написан с точки зрения мелочей имплементации, но конечно названия переменных и повторное их использование с другим смыслом не добавляет понятности алгоритму. Я переименовал переменные, разделил их где надо и снабдил комментариями. /* Finds longest strictly increasing subsequence. O(n log k) algorithm. */ template vector find_lis(vector &data) { // решаем задачу итеративно. сначала рассматриваем только первый элемент // затем добавляем элементы по одному
// (бывший массив p) // вот это интересная штука. тут для каждого индекса i мы рассматриваем // наилучшую из подпоследовательностей, заканчивающихся **на этом элементе**, // и записываем в этот массив индекс предыдущего элемента. // мы пользуемся таким важным свойством: для наилучшей подпоследовательности, // заканчивающейся на i-ом элементе, её кусок без финального элемента обязан быть // наилучшей подпоследовательностью, заканчивающейся на соответствующем // элементе. поэтому для хранения наилучших подпоследовательностей достаточно // лишь одного предыдущего индекса vector previdx(data.size());
// бывший массив b // а здесь мы храним индексы тех элементов, которые **в принципе** могут стать // чьим-то предыдущим элементом в наилучшей последовательности. // список хранится в таком порядке, чтобы соответствующие данные // были отсортированы (чтобы можно было искать двоичным поиском) vector possibleprev;
// тривиальный случай if (data.size() < 1) return vector();
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 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; } Всё!