动态规划求解最大递增子序列

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

然后对这些元素求最大值。

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

- kafka

---

为什么要使用动态规划解决方案，其运行时间复杂度为O(N^2)，而已经存在一种二分查找解决方案，可以在O(N logN)内完成呢？请参见https://dev59.com/MG025IYBdhLWcg3wPzbL。 - DU Jiaen

Answer 1

这里有一个提示：算法中将要保持的循环不变式是一个变量 k，它表示最长递增子序列的起始索引。因此，当你遍历整数序列 [0...n] 时，相应地增加 k 的值。

- Jeffrey Greenham

Answer 2

// 给定一个整数数组，找到最长递增子序列的长度并打印出该序列。

int longsub (int a[], int len) {

    int localsum = 0;
    int i = 0;
    int begin = i;
    int localsublen = 1;
    int globalsunlen = 0;
    int end = i;

    for (i=1; i< len; i++)    {

        if (a[i] > a[i-1]) {
              localsublen++;
        }
        else {
            newbegin = i;
            localsublen = 1;
        }

        if (localsublen > globalsublen)    {
            begin = newbegin;
            end = i;
            globalsublen = localsublen;
        }
    }

    for (i=begin;i <= end; i++)    
        printf ("%d.\n",a[i]);


}

- asim kadav

---

我认为这不正确。例如，考虑[1,5,6,2,7]，你的代码会得到[1,5,6]，但实际上最优解是[1,5,6,7]。 - DU Jiaen