php - LIS - PHP の最長増加サブシーケンス アルゴリズム O(nlogn)

Question

私の問題の解決策がどこにも見つかりません:(。誰かが私を助けて、コメント付きでこのアルゴリズムを見つける（または書く）ことができますか?

ビッグありがとう！

Answer 1

ベクトル 'v[x] = y' を保持します。ここで、y は、長さ x の最長増加サブシーケンスを与える元のシーケンスの最小要素です。もともと持っているのは だけv[0] = -infです。

要素のシーケンスをトラバースし、バイナリ検索を使用aしてベクトルで検索します。v正確にはわかりませんaが、そのような最大xのものv[x] <= a(< 厳密に増加している場合)。したがって、a で終わる最長の増加部分列は長さになりx+1ます。ここで a に更新v[x+1]します (a よりも小さくすることはできません。それ以外の場合は、検索に returnx+1が必要です)。ベクトルを拡張する必要がある場合があります。

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