algorithm - 次のアルゴリズムの正しさを証明する方法

Question

問題は、任意の配列の LIS (最長増加部分列) を見つけることです。元。[] = {10,9,7,8,9}; 長さ=3; {7,8,9}

したがって、nlognで行う1つの方法は

1. 配列をソートする
2. 2 つの LCS を取り、結果として LIS が得られます。

今、私はそれを行う方法を理解しました。しかし、それが正しいことをどのように証明するのでしょうか。ここで MI を適用する方法は?

Answer 1

あなたの場合、誘導の必要はありません。3つのことを示す必要があります。

• 結果のメソッドは増加するシーケンスをキャプチャします-それがソートされた配列の一部であるという事実から直接来ます
• 結果のサブシーケンスは入力配列に存在します - LCS の定義から直接得られます (共通サブシーケンス)
• 増加するサブシーケンスはもうありません - 最長のシーケンスが入力シーケンス (定義による) とソートされた配列の両方に存在する必要があることを簡単に示すことができるため、LCS によっても分析されるため、返されたものよりも長くなることはありません。 LCSによる。