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

#массивы #вектор #cpp

Есть задачка: Дана последовательность целых чисел. Найти ее максимальную возрастающую
подпоследовательность. Нашла решение в интернете, но никак не могу вникнуть(
+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\n", seq[lis[i]]);
 getch();
    return 0;
}
    

Ответы

Ответ 1

Смотрите, всё не так уж сложно.
Код отлично написан с точки зрения мелочей имплементации, но конечно названия переменных
и повторное их использование с другим смыслом не добавляет понятности алгоритму.
Я переименовал переменные, разделил их где надо и снабдил комментариями.
/* 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;
}

Всё!


Ответ 2

Видимо я тут чего-то важного не понимаю.
#include 

struct range {
  int start, end;
};

// inclusive range
struct range
max_gtseq (int *a, int n)
{
  struct range result = {0, 0};
  int max = 0, start = 0, end = 0;

  for (int i = 0; i < n - 1; i++)
    if (a[i] < a[i + 1])
      end++;
    else {
      if (end - start > max) {
        max = end - start;
        result.start = start;
        result.end = end;
      }
      end = start = i + 1;
    }

  if ((n - 1) - start > max) {
    result.start = start;
    result.end = n - 1;
  }

  return result;
}

int
main (int ac, char *av[])
{
  int x[] = {1, 2, 3, 10, 1, 2, 100, 1, 2, 3, 4, 5, 6, 0}; //{10, 9, 8};

  struct range r = max_gtseq(x, sizeof(x) / sizeof(x[0]));

  printf ("start = %d end = %d\n", r.start, r.end);

  return puts("End") == EOF;
}

Неужели такой тривиальный однопроходный алгоритм не работает?