問題タブ [lis]

私は整数のセットを持っています。動的計画法を使用して、そのセットの最長増加サブシーケンスを見つけたいです。

数列が与えられ、与えられた入力から最長増加部分列を見つける必要があります（連続である必要はありません）。

これへのリンク（ウィキペディアで最も長く増加しているサブシーケンス）を見つけましたが、さらに説明が必要です。

誰かがO（n log n）の実装を理解するのを手伝ってくれるなら、それは本当に役に立ちます。例を挙げてアルゴを説明できれば、それは本当にありがたいことです。

私は他の投稿も見ましたが、私が理解していなかったのは次のとおりです。i = 1、2、...nの場合はL= 0：X [M[j]]<Xとなる最大の正のj≤Lの二分探索[i]（またはそのような値が存在しない場合はj = 0に設定）上記のステートメント、どこから二分探索を開始しますか？M []、X []を初期化する方法は？

LIS:ウィキペディア

私が理解できないことが1つあります：

X[M[i]] が非減少シーケンスなのはなぜですか?

This was the program I done for finding the longest increasing subsequence. I am getting the length of the subsequence correctly but i am not getting the sequence correctly. I think there may be a problem with the the last for loop which contains the variable k, but I cant figure it out. please help me.

ウィキペディアで指定された最長増加サブシーケンスの擬似コードを次に示します

コードの仕組みは理解できました。私が理解できない唯一のことは、このステートメントの必要性です(if j == L or X[i] < X[M[j+1]]:)私は多くの例でアルゴリズムを実行しようとしましたが、私が理解できることすべてのケースで j == L または X[i] < X[M[j+1]] のいずれかであり、if ステートメントは常に True と評価されます。if ループが false で、アルゴリズムに必要な例を教えてください。

気になることがあります。この情報を指示として持つ建物の橋の問題を解決しようとしています。

橋
を架ける 水平方向の川が中心を通過する 2 次元マップを考えてみましょう。南岸には x 座標 a(1) ... a(n) の n 個の都市があり、北岸には x 座標 b(1) ... b(n) の n 個の都市があります。
2 つの橋が交差しないように、できるだけ多くの都市の南北のペアを橋で接続する必要があります。都市を接続する場合、北岸の都市 i と南岸の都市 i のみを接続できます。」

私はスタック オーバーフローについて調査し、次のような非常に役立つトピックを見つけました
。 動的計画法を使用して最長増加サブシーケンスを
決定する方法は?

しかし、私が LIS を思いついたとき、1 つのサンプル リストを手で解決しようとしました。私が持っているとしましょう

ソート後サザンバンク

LIS の長さは "5" であると想定されていますが、実際には最初のリストでは、(3,2,1) を作成できるブリッジは 3 つだけです。それで、私はLISを誤解しましたか、それとも橋の問題を構築するのにうまくいかない例外はありますか?

The Hitchhiker's Guide to the Programming Contests に記載されているアルゴリズムを見つけました(注: この実装では、リストに重複がないことを前提としています):

O(NlogN) で最も長く増加する部分列を見つけるアルゴリズムです。いくつかのテストケースで動作させようとすると、動作するようです。しかし、私はまだその正当性ロジックを理解できませんでした。また、私にはそれほど直感的に見えません。

このアルゴリズムが正しく機能する理由について洞察を得るのを手伝ってくれる人はいますか?

SPOJ からの問題文は次のとおりです。通常の DP ソリューションから始めましたが、n^2 の時間がかかり、制限時間を超えることは避けられませんでした。

問題に対する nlogn ソリューションに出会いました。これがそのソリューションです。

最長増加サブシーケンスの長さを見つける必要がある場合、またはシーケンスの 1 つも見つけなければならない場合、このソリューションはうまく機能します。しかし、あるシーケンスまたは他のシーケンスの一部であるすべての要素を見つける必要がある場合は、いくつかのストレージやその他のことを行い、このソリューションに到達しました.

現在、これは SPOJ エンジンによって予期されていましたが、受け入れられている他のソリューションを見ると、私のプログラムは 0.48 時間かかり、他のプログラムは 0.04 時間しかかかりません。

可能であれば、ソリューションを改善する方法を教えてもらえますか?

私がソリューションで行っていることは、出力配列に現在の数値だけでなくリスト全体を格納していることです。親では、各数値が出力の一部になるため、すべての親を維持しています。配列。

最終的な配列は、その数値が LIS に属するかどうかのブール値を格納する最終的な整数配列にすぎません。

ありがとう

PS ideone.com へのリンクにはコードを添付する必要があると記載されているため、ここにコード自体を貼り付けます。