各要素から最も長い部分シーケンスを増やす

Question

リスト{x_i}があれば、開始要素がサブシーケンスに含まれるように各要素から始まるlongest increasing subsequenceを探したいと思う。

これを実行する明らかな方法は、O（n^2 logn）とすると、各要素に対して通常の最長増加サブシーケンスアルゴリズムを実行することです。これは殴られますか？

Answer 1

DPを使用してO（n^2）にすることができます。

入力X1、X2、...、XN

は、F1、F2をしてみましょう...、FN要素i番目から始まる最長増加するシーケンスの長さ。としますあなたは長さに加えて、実際の配列をしたい場合は、別の変数G1のトラックを保持

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

、今1

にそれらのすべてを初期化し、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; 

}

これは、時間計算量がこれよりややNよりエレガント（ペアとのマップを使用して）を思い付くであろう^ 2.I溶液C++コードです。それはnlogn order.Iはデータの密度に依存するので、私はここでコードを記述しませんでした。データが密集している場合は、私はそうでなければ、それは常に正常に動作しますそのアプローチを記述します。