数値の配列が与えられ、質問は、長さがlis-1の増加するサブシーケンスの総数を見つけることです。ここで、lisはその特定の配列の長さです。 Largest Increasing sub-sequence
例:配列が であるとし5 6 3 4 7 8ます。ここで、lis = 4です。したがって、lis-1 = 3です。したがって、サブシーケンスの総数は次の8とおりです。
5 6 7
5 6 8
3 4 7
3 4 8
3 7 8
6 7 8
5 7 8
4 7 8
誰かがこのアルゴリズムのアイデアを教えてくれますか?私はそれを理解することができません.
動的プログラミングを使用しなくても、この問題を解決できます。配列の要素が一意であると仮定すると (重複のアイデアをさらに拡張できます)、アイデアは、セット (一意の要素を昇順で格納する) を維持し、このセットを埋めることです。配列要素を処理しています。現在の要素でセットを拡張できる場合 (現在の要素がこれまでに見た最大の要素であることを意味します)、この要素をセットの最後に追加します。そうでない場合、現在の要素はセット要素のいずれかを置き換えます現在の要素に適合する場所になります。このようにして、セットの長さが lis-1 のときにセットを追跡し、カウンターを増やします。お役に立てば幸いです。さらに説明が必要な場合はお知らせください。
動的プログラミングのアプローチがあると思います。シーケンス内の各ポイントについて、長さ k のポイントで終了するサブシーケンスの数を保持する配列を保持します。
各ポイントで、配列の内容からその左側の配列の内容と、対応するサブシーケンスのポイントを計算できます。現在の値よりも小さいシーケンス値を持つ左側のポイントから配列値を追加します。たとえば、count[currentPos ][k+1] += count[左位置][k].
最後に、配列内のゼロ以外の最も高い位置は、最大の増加するサブシーケンスの位置をマークし、そのすぐ下の値は、長さが 1 つ短い増加するサブシーケンスのカウントを示します。