algorithm - 找到所有可能的最长递增子序列

我想在给定的字符串中找到所有可能的最长递增子序列。

例如:给定的字符串是 qapbso
这里最长递增子序列的长度为 3。
我想找到长度为 3 的所有可能的最长子序列。即“abs”、“aps”、“abo”。

我正在使用动态规划，但我只得到一个 LIS。我想列出所有这些。

最佳答案

因此，典型的 DP 解决方案将生成一个数组，其中您知道从给定位置开始的最长可能子序列是什么，假设您有一个长度为 n 的数组，其中 dp[i] 存储最长非的长度- 以索引为 i 的元素开始的递减子序列。

现在打印所有 LNDSS(最长非递减子序列)最容易使用递归完成。首先通过选择 dp 中的最大值来找到 LNDSS 的实际长度。接下来从 dp 中具有最大值的 dp 中的每个元素开始递归(这些可能不止一个)。从给定索引的递归应该打印从当前索引开始的长度等于值 dp[i] 的所有序列:

int st[1000];
int st_index
void rec(int index) {
  if (dp[index] == 1) {
    cout << "Another sequence:\n";
    for (int i = 0; i < st_index; ++i) {
      cout << st[i] << endl;
    }
  }
  for (int j = index + 1; j < n; ++j) {
    if (dp[j] == dp[index] - 1 && a[j] >= a[index]) {
      st[st_index++] = a[j];
      rec(j);
      st_index--;
    }
  }
}

这是 C++ 中的示例代码(希望在其他语言中也能理解)。我有一个名为 stack 的全局堆栈，用于保存我们已经添加的元素。假设 LNDSS 中的元素永远不会超过 1000 个，它的大小为 1000，但这可以增加。该解决方案没有最好的设计，但我专注于使其简单而不是精心设计。

希望这可以帮助。

关于algorithm - 找到所有可能的最长递增子序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9554266/