algorithm - 查找给定长度的递增子序列的总数

Question

给定一个数字数组，问题是找到长度为lis-1的递增子序列的总数，其中lis是该给定数组的长度。 Largest Increasing sub-sequence

示例：假设数组是5 6 3 4 7 8. 在这里，lis = 4。所以，lis-1 = 3。因此，子序列的总数8如下：

5 6 7
5 6 8
3 4 7 
3 4 8
3 7 8
6 7 8
5 7 8
4 7 8

有人可以给我这个算法的想法，我无法弄清楚。

Answer 1

即使不使用动态编程，您也可以解决此问题。假设数组的元素是唯一的（您可以进一步扩展重复的想法），想法是您维护一个集合（以递增的顺序存储唯一元素）并填充这个集合，同时您正在处理数组元素。如果您可以通过当前元素扩展集合（意味着当前元素是迄今为止看到的最大元素），那么您将此元素附加到集合的末尾，否则当前元素将替换其中一个位置的集合元素将是您适合当前元素的位置。这样，当它的长度为 lis-1 时跟踪 set 并增加计数器。我希望这会有所帮助，如果您需要更多解释，请告诉我。

Answer 2

我认为有一种动态编程方法。对于序列中的每个点，保留一个数组，其中包含在该点终止长度为 k 的子序列的数量。

在每一点，您都可以从其左侧数组的内容和子序列的相应点计算出其数组的内容：从左侧的点添加数组值，其中序列值小于当前值，例如 count[currentPos ][k+1] += 计数[leftPos][k]。

最后，数组中最高的非零位置标记了最大递增子序列的位置，而恰好低于该位置的值给出了长度短一的递增子序列的计数。