除算と征服を使用して最長増加するサブシーケンスを見つける

Question

先週のインタビューで、私は上記の質問を受けました。予想通り、私は正しく答えられませんでした。アルゴリズム。私は動的プログラミングに堪能ではありませんが、私はこのアルゴリズムを設計すると仮定して、私はそれにどのようにアプローチすべきですか？

と仮定、私は他の分裂からアイデアを取るとMergeSortのようなアルゴリズムを征服などソリューション何かデザイン：2等分で

1. 分割シーケンスを。
2. 2つの半分の中で最も長い増加するサブシーケンスを見つけます。
3. 2つの半分を結合します。

明らかに欠けている部分がありますが、ここからどのように進んでいますか？

Answer 1

あなたの提案はうまくいきません。なぜなら、両方の半分の最長の配列は通常連続していないため、半分を結合するときに長い配列が存在する可能性があるからです。

次のようにして、この問題を解決することができます両方の半分で

• を、最長増加サブシーケンスを見つけ、LとRましょう。
• 両方の半分の場合、左揃えの最長増加サブシーケンスを見つけます.LLとRLとします。

• の両方の半分で、右揃えの最長増加サブシーケンスを見つけてください。

• 最長の場合、L、R、LR + RLが増加するシーケンスを形成する場合は、L、R、LR + RLの最長を維持します。

• 左寄せの場合、LLを保持するか、または左のサブシーケンス全体+ RLが増加するサブシーケンスを形成する場合は、RL。
• 右寄せの場合は、これが増加するサブシーケンスを形成する場合、RRまたはLR +右全体のサブシーケンスを保持します。

これらの操作はすべて1回の再帰処理で実行されます。 2つのサブシーケンスを連結するとき、それらが増加するサブシーケンスを形成するかどうかを確認するだけで、対向する要素の比較が行われます。