2つの数値を持つLIS（Longest Increasing Subsequence）

Question

2つの数値を使用してLISの長さを見つける方法。 例えば、 [（1,2）（7,8）（3,4）（5,6）] 上記の配列シーケンスでは、 ）（3,4）（5,6）] アイデア？

Answer 1

は、次の2つの修正を加えて、標準LIS problemのための任意のalgorithmを使用することができます。

1. は、第二の数は厳密に最初の数よりも大きくはない任意のペアを捨てます。
2. AおよびB（すなわちA < B）では、最初のLISを見つけ、その基数を計算しなければならないB.

Answer 2

タプル自体の最初と2番目の数字は、常に昇順です（これはあなたの例のようです）。これは基本的に若干の変更以外にregular LIS algorithmと異なるものであってはいけません。最後の数が現在のタプルの最初の数よりも少ない現在のタプル。ダイナミックプログラミングを使用して、各シーケンススポットの最大LISと先行タプルをキャッシュします。

Answer 3

の最初の数の第二の数を比較する必要があるペアの比較演算子

Answer 4

私はあなたがいることを、小さな例外を除いて標準LISアルゴリズムを使用することができると思う - あなたは私がインデックスi + 1でインデックスを比較するとき

- I + 1の低い値で、iの上限値を比較します。

EDIT：これはもちろん、すべての範囲が最初に小さい番号を持ち、次に高い番号を持つと仮定します。

Answer 5

問題をグラフでモデル化します。各タプルはノードになることができます。第1のタプルが第2のタプルよりも厳密に小さい場合（ここでは、「少ない」とはタプルの両方の値がより少ないことを意味する）、あるノードから別のノードへ有向エッジが存在する。

このグラフでは、最長増加サブシーケンスが最長のパスになりました。このグラフにサイクルは存在しないことに注意してください（つまり、DAGです）。 DAG内の最長のパスは、動的プログラミング（wikipediaを参照）によって見つけることができます。

Answer 6

私はあなたが何を頼んでいるのか分かりませんが、< cとb < d（これは、 。

in another SO threadと記載されている標準の動的プログラミング手法を適用することで、これはO（N^2）時間で簡単に解決できます。

古典的なO（N log N）solution to the standard LIS problemは、いくつかの難しさで、ペアのLIS問題の準二乗解を与えるために拡張することができます。可能なすべての長さに対して最小値を1つ記憶するだけではありません。各長さのすべての最小ペアを含む「階段状」構造、すなわち、hereと記載されているデータ構造のN個までのコピーを維持しなければならない。次に、O（log N）時間内にこの構造の1つのコピーを照会し（バイナリサーチステップのためにO（log^2 N）時間を与える）、O log^2 N）時間である。これは私が問題に知っている最速の解決策です。

Answer 7

単純配列のLISを見つける場合に実行します。ただ1つの比較を行うだけで、両方の要素を比較してください。それはLISにO（n^2）時間の複雑さを与えます。