LIS - PHPで最も長くなる部分シーケンスアルゴリズムO（nlogn）

Question

私の問題の解決策はどこにも見つかりません:( 誰かが私に助けてくれて、このアルゴリズムをコメントで見つけることができますか？ できませんそれ自分自身。私はそれに少なくとも3時間と何を過ごした。

BIGありがとう！

Answer 1

がベクトルキープyが与えられる元のシーケンスの最小の要素である「Vの[X] = Y」長さxの最長増加部分列。最初はv[0] = -infしか持っていません。

e aを検索し、バイナリ検索を使用してベクトルvを参照してください。 aは正確に見つかりませんが、最大値はxで、v[x] <= a（厳密に増加している場合は<）です。したがって、長さが長くなるサブシーケンスは、長さがx+1になります。 v[x+1]をa（それより小さくすることはできません）に更新してください。さもなければ、あなたの検索はx+1の戻り値になるはずです。ベクトルを拡張する必要があります。

LISの長さはベクトルのサイズです。ソリューションを再構築する必要がある場合は、どのポジションを使用したかを把握してください。