[解決済み】動的計画法を用いて，最も長く増加する部分列を決定する方法とは？

質問

整数の集合がある。を見つけたい。 最長増加部分配列 その集合の動的計画法を使って

どのように解決するのですか？

まず、最も簡単な解決策を説明しよう。これはO(N^2)であり、Nはコレクションの大きさである。また、O(N log N)の解も存在するが、これも説明する。見てください。 こちら の項を参照してください。

配列の添字を0からN - 1までとし、次のように定義します。 DP[i] の要素で終わるLIS（Longest Increasing Subsequence）の長さです。 i . を計算するために DP[i] のすべてのインデックスを調べます。 j < i の両方をチェックし、もし DP[j] + 1 > DP[i] と array[j] < array[i] (増加するようにしたい)。もしこれが本当なら，現在の最適な DP[i] . 配列の全体最適を求めるには，配列の中の DP[0...N - 1] .

int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;

for (int i = 1; i < N; i++)
{
   DP[i] = 1;
   prev[i] = -1;

   for (int j = i - 1; j >= 0; j--)
      if (DP[j] + 1 > DP[i] && array[j] < array[i])
      {
         DP[i] = DP[j] + 1;
         prev[i] = j;
      }

   if (DP[i] > maxLength)
   {
      bestEnd = i;
      maxLength = DP[i];
   }
}

私は、配列 prev これは、後で長さだけでなく実際のシーケンスを見つけることができるようにするためです。から再帰的に戻るだけです。 bestEnd を使ったループで prev[bestEnd] . その -1 の値は、停止を意味します。

さて、次はより効率的な O(N log N) の解決策になります。

Let S[pos] は、長さの増加する数列を終了する最小の整数と定義されます。 pos . ここで、すべての整数 X を入力し、次のようにします。

1. もし X の最後の要素です。 S を追加し、さらに X の末尾に S . これは本質的に、私たちが新しい最大の LIS .

2. の中で最も小さい要素を探します。 S である。 >= より X に変更し、それを X . なぜなら S はいつでもソートされるので、バイナリサーチを使って要素を log(N) .

総実行時間 N 整数とそれぞれのバイナリサーチ - N * log(N) = O(N log N)

では、実際の例をやってみましょう。

整数のコレクション。 2 6 3 4 1 2 9 5 8

ステップス

0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS

つまり、LISの長さは 5 (Sの大きさ）。

を再構築するために、実際の LIS では、再び親配列を使用します。 では parent[i] をインデックスとする要素の前身である i の中で LIS をインデックスとする要素で終了します。 i .

よりシンプルにするために、配列の中に S 実際の整数ではなく、集合の中のインデックス(位置)です。我々は {1, 2, 4, 5, 8} を保持し {4, 5, 3, 7, 8} .

それは、input[4] = 1 入力[5]は 2 , input[3] = 4 , input[7] = 5 , input[8] = 8 .

親配列を適切に更新すれば、実際のLISは。

input[S[lastElementOfS]], 
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................

さて、肝心の親配列はどのように更新するのでしょうか？選択肢は2つあります。

1. もし X の最後の要素です。 S であれば parent[indexX] = indexLastElement . これは、最新の要素の親が最後の要素であることを意味します。私たちはただ X の末尾にある S .

2. の最小の要素のインデックスを探します。 S である。 >= より X に変更し、それを X . ここで parent[indexX] = S[index - 1] .