最长递增子序列算法中的节点结构（Jacobson & Vo）

Question

我无法理解 Jacobson 和 Vo 的论文 "Heaviest Increasing/Common Subsequence Problems" 中用于计算完整最长递增子序列 (lis) 的节点结构。

这是论文中的伪代码：

是什么意思

node is an auxiliary array that, for each element in L, contains a record of an element that precedes this element in an increasing subsequence. The function newnode() constructs such records and links them into a directed graph. At the end of the algorithm, we can search from the maximal element of L to recover an LIS of sigma.

？你会如何实现这个结构？

是否必须构建一个有向图，其中所有序列元素为顶点（加上一个零顶点）和边“\sigma_i -> s”，然后搜索最长的路径开始在 L 的最大元素处（并以零结尾）？有没有更有效的获取完整lis的方法？

我的第二个问题：这个算法和wikipedia中描述的算法一样快吗？如果不是：我是否也可以修改维基百科的算法来计算论文中描述的最重的公共子序列？

Answer 1

我会用数组实现数组，将图形实现为具有结构共享的单链表。也就是说，在通用 C++ 中，

#include <algorithm>
#include <iostream>
#include <memory>
#include <utility>
#include <vector>

template <typename T>
struct Node {
  explicit Node(const T& e) : element(e) {}

  T element;
  std::size_t index = 0;
  Node* previous = nullptr;
};

template <typename T, typename Compare>
std::vector<T> LongestIncreasingSubsequence(const std::vector<T>& elements,
                                            Compare compare) {
  if (elements.empty()) {
    return {};
  }
  std::vector<std::unique_ptr<Node<T>>> node_ownership;
  node_ownership.reserve(elements.size());
  std::vector<Node<T>*> tableau;
  for (const T& element : elements) {
    auto node = std::make_unique<Node<T>>(element);
    auto it = std::lower_bound(tableau.begin(), tableau.end(), node.get(),
                               [&](const Node<T>* a, const Node<T>* b) {
                                 return compare(a->element, b->element);
                               });
    if (it != tableau.begin()) {
      auto previous = it[-1];
      node->index = previous->index + 1;
      node->previous = previous;
    }
    if (it != tableau.end()) {
      *it = node.get();
    } else {
      tableau.push_back(node.get());
    }
    node_ownership.push_back(std::move(node));
  }
  Node<T>* longest = *std::max_element(
      tableau.begin(), tableau.end(),
      [](Node<T>* a, Node<T>* b) { return a->index < b->index; });
  std::vector<T> result(longest->index + 1);
  for (; longest != nullptr; longest = longest->previous) {
    result.at(longest->index) = longest->element;
  }
  return result;
}

int main() {
  for (int x : LongestIncreasingSubsequence(
           std::vector<int>{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3},
           std::less<int>())) {
    std::cout << x << '\n';
  }
}

如果您有幸使用具有垃圾收集功能的语言工作，则可以忽略 node_ownership 和 std::move 的业务。

这是一个 Python 版本。

import bisect


def longest_increasing_subsequence(elements):
    elements = list(elements)
    if not elements:
        return []
    # Build the tableau
    tableau_elements = []
    tableau_indexes = []
    predecessors = []
    for i, element in enumerate(elements):
        j = bisect.bisect_left(tableau_elements, element)
        predecessors.append(tableau_indexes[j - 1] if j > 0 else None)
        if j < len(tableau_elements):
            tableau_elements[j] = element
            tableau_indexes[j] = i
        else:
            tableau_elements.append(element)
            tableau_indexes.append(i)
    # Find the subsequence lengths
    lengths = []
    for i, predecessor in enumerate(predecessors):
        lengths.append(1 if predecessor is None else lengths[predecessor] + 1)
    # Extract the best subsequence
    best = max(range(len(lengths)), key=lambda i: lengths[i])
    subsequence = []
    while best is not None:
        subsequence.append(elements[best])
        best = predecessors[best]
    subsequence.reverse()
    return subsequence


print(longest_increasing_subsequence([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3]))

最长递增子序列算法中的节点结构（Jacobson & Vo）

Node structure in longest increasing subsequence algorithm (Jacobson & Vo)

algorithm

lcs

lis