2

配列 = {2,5,7,8,10} とします。要素がその前のすべての要素の合計よりも小さくならないように、最長増加サブシーケンスの長さを見つける必要があります。

この場合、答えは {2,5,7}、{2,5,8}、または {2,8,10} になります。長さ = 3
これは O(n^2) で簡単に解けます。LIS の長さは O(n log n) で確認できます。問題は長さだけなので、この問題も O(n log n) で解けると思います。しかし、どうすればそれを行うことができますか?

4

2 に答える 2

0

  1. 次のO(N^2)ような動的プログラミングソリューションがあります。

    • 最初の要素の 1 つで終了し、正確に要素で構成されるf(i, j) 「正しい」サブシーケンスが持つことができる最小の合計を とします。ij

    • 基本ケースはf(0, 0) = 0(空の接頭辞、要素なし)

    • 遷移はf(i, j) -> f(i + 1, j)(新しい要素を追加しない) と
      f(i, j) -> f(i + 1, j + 1) if a[i] > f(i, j)(i可能であれば、サブシーケンスの最後に -th 要素を追加する) です。

このソリューションの正しさは自明です。

  1. クールな事実: let be は要素Aの「正しい」サブシーケンスです。kの最後の要素Aよりも小さくないmax(1, 2^(k-2))(証明: と の場合ですk = 1。k = 2これで帰納法と という事実を使用できます1 + sum i = 0 .. k of 2^k = 2^(k+1))

  2. したがって、上記の動的計画法ソリューションではj範囲が広がるため、 で機能します。0..log MAX_A + CO(N * log MAX_A)

O(N * log MAX_A)ではありませんO(N log N)が、このソリューションは実用的な目的には適しています。

于 2016-12-24T17:49:33.820 に答える
0

実際には、DP ソリューションはまったく必要ありません。
まず、数値を減少しない順に並べ替えます。そして、左から右にループします。現在の合計を追跡します。
次の数が合計より小さくない場合は、それを LIS に追加します。それ以外の場合は、次の番号に進みます。
貪欲な解が最適解であることは証明できます。自分で証明してください;）

于 2016-12-25T09:42:51.973 に答える