每个元素的最长递增子序列

Question

给定一个列表{x_i}，我想要找到从每个元素开始的最长的递增子序列，使得起始元素包含在子序列中。

最明显的方法是对每个元素执行通常的最长递增子序列算法，给出O(n^2logn)。这能打吗？

Answer 1

您可以使用DP并将其降至O(n^2)。

设输入为x1,x2,...,xn

设f1,f2,…,fn是从第i个元素开始的最长递增序列的长度。将它们全部初始化为1。

for i = n-1, n-2, .... , 1:
    for j = i,i+1,...,n:
        if x[i]<x[j]:
            fi=max(fi, fj+1)

for i = n-1, n-2, .... , 1:
    for j = i,i+1,...,n:
        if x[i]<x[j]:
            if fi<fj+1:
                fi=fj+1
                gi=j