algorithm - 动态规划的最大递增子序列

Question

问题如下:给定一个由 n 个整数组成的序列 L 不一定不同，编写一个算法来计算最大长度的递增子序列:

我开发的递归方程是这样的:

我从 0 开始索引:

If j = n opt(j) = 0 (base case)
otherwise opt(j) = max j <i <= n such that Lj <Li = {opt(i) +1}

你认为这样做对吗？这个典型问题的标准解决方案是首先计算序列中所有元素的以 Li 结尾的最大递增子序列，然后计算这些值的最大值，即:

if i = 1 opt (i) = 1
otherwise opt (i) = max 1 <= j <= i-1 and Lj <Li = {opt (i)} +1

然后是这些元素的最大值。

所以我想知道您是否认为我的解决方案是正确的。

Answer 1

这里有一个提示:算法中试图保留的循环不变量是一个变量，k = 最长递增子序列开头的索引。因此，当您遍历整数序列 [0...n] 时，您会相应地增加 k 值。