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

Question

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

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

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)

如果除了长度之外还需要实际序列，请跟踪另一个变量 g1,g2, ..., gn，其中 gi 是要遵循的下一个元素。将 gis 初始化为 NULL。

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

一旦你有了 gs，我会让你弄清楚如何从特定位置开始枚举序列。

Answer 2

更有效的算法将依赖于每次迭代共享相同的数据结构，而不是每次都重新启动算法。一种方法是找到输入列表反向的最长递减子序列。这应该为您提供一个数据结构，使您可以恒定时间访问每个元素的前任，以及从该元素开始的子序列的长度。

对于每个起始元素：如果它在最长的递减子序列中，则跟随其前辈到最后。如果不是，则找到其右侧较大且具有最多前辈的元素，并遵循该元素的前辈。

这将给出 O(N^2) 的最坏情况时间复杂度，但至少需要这样才能输出结果。

Answer 3

int main(){

int arr[]={1,10,5,12,17,18,19};
int t[]={1,0,0,0,0,0,0};
int i,j;
vector<int>v[7];
v[0].push_back(1);       
for(i =1;i<7;i++){

    for(j =0;j<i;j++){
          if(arr[j]<arr[i]){

             if(t[j]>=t[i]){
                 t[i]=t[j]+1;
                 v[i].push_back(arr[j]);
             }
          }
     }
     if(i==j){
        v[i].push_back(arr[i]);
     }
}

for(i=0;i<7;i++){
    for(j=0;j<v[i].size();j++){
        cout<<v[i][j]<<" ";
    }
    cout<<endl;
}


return 0;

}

这是 C++ 代码，时间复杂度是 N^2。我会想出更优雅（使用 map 和 pair）的解决方案，而不是这个。那将是 nlogn 顺序。我没有在这里编写该代码，因为这将取决于数据密度。如果数据密集，那么我将编写该方法，否则它将始终正常工作。