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

より効率的なアルゴリズムは、アルゴリズムを毎回再起動するのではなく、反復ごとに同じデータ構造を共有することに依存します。これを行う 1 つの方法は、入力リストの逆の最長減少サブシーケンスを見つけることです。これにより、各要素の先行要素への一定時間のアクセスと、その要素から始まるサブシーケンスの長さを提供するデータ構造が得られます。

各開始要素について: それが最も長く減少するサブシーケンスにある場合は、その先行要素を最後までたどります。そうでない場合は、より大きく、その右側にあり、先行要素が最も多い要素を見つけて、その要素の先行要素に従います。

これにより、最悪の場合の時間の複雑さが 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 です。これよりもエレガントな (ペアでマップを使用する) ソリューションを考え出します。それはnlognオーダーになります.データ密度に依存するため、ここではそのコードを書きませんでした.データが密集する場合は、そのアプローチを書きます。