algorithm - サブシーケンスは連続する必要がありますか

Question

私は動的プログラミングが初めてで、最長増加部分列 (LIS) 問題を読んでいました。

ソリューションは、シーケンスが元の配列のように連続している必要はないと述べました。要素は途中でスキップできます。しかし、私は別の印象を受けました。

この混乱を明確にするのを手伝ってください。

例を挙げてみましょう: a = {10,22,9,33,55,66,12,90} LIS は{10,22,33,55,66,90} => 6

しかし、私はそうなると思った{33,55,66}

ありがとう

Answer 1

サブシーケンスは連続している必要はありません。サブシーケンスは、配列から 0 個以上の要素を削除することによって形成されます。一方、サブアレイは常に連続しています。あなたの例を見てみましょう：

a = {10,22,9,33,55,66,12,90}

ここで、{10,22,33,55,66,90}は最長増加部分列で{33,55,66}あり、 は最長増加部分配列です。

したがって、基本的に答えているのは、サブアレイの最長増加問題の解決策です。