Longest NlogNのサブシーケンスの長さを増やす[Algoを理解する]

Question

Problem Statement：目的は、nlogn時間で最も長くなるサブシーケンス（連続していない）を見つけることです。

アルゴリズム：ここで説明するアルゴリズムは理解しています。 http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/。

私が理解できなかったことは、次のコードの末尾に何が格納されているかです。例えば

int LongestIncreasingSubsequenceLength(std::vector<int> &v) { 
if (v.size() == 0) 
    return 0; 

std::vector<int> tail(v.size(), 0); 
int length = 1; // always points empty slot in tail 

tail[0] = v[0]; 
for (size_t i = 1; i < v.size(); i++) { 
    if (v[i] < tail[0]) 
     // new smallest value 
     tail[0] = v[i]; 
    else if (v[i] > tail[length-1]) 
     // v[i] extends largest subsequence 
     tail[length++] = v[i]; 
    else 
     // v[i] will become end candidate of an existing subsequence or 
     // Throw away larger elements in all LIS, to make room for upcoming grater elements than v[i] 
     // (and also, v[i] would have already appeared in one of LIS, identify the location and replace it) 
     tail[CeilIndex(tail, -1, length-1, v[i])] = v[i]; 
} 

return length; 
} 

入力は{2,5,3、11,8,10,13,6}である場合、 コードは6 として正しい長さを与えるが、尾は2,3を記憶します、6,8,10,13。

だから私は尾に格納されているものを理解したいのですか？これはこのalgoの正しさを理解するのに役立ちます。

Answer 1

tail[i]は、長さがi+1の増加するサブシーケンス（IS）の最小限の最終値です。

だから、tail[0]は「最小値」であり、なぜ現在の値が現在の最長シーケンスの終了値よりも大きいときにLIS（length++）の値を大きくすることができるのです。

のあなたの例では、入力の開始値であると仮定する：

入力= 2、5、3、7、11、8、10、13、6、... 9後

私たちのアルゴリズムtailの手順は、次のようになります。
尾= 2、3、6、8、10、13、...

何tail[2]手段のでしょうか？これは、長さが3の最良ISがtail[2]で終わることを意味します。さらに、長さが4で、tail[2]より大きい数字で拡張することができます。

tail[0] = 2、IS length = 1：、5、3、7、11、8、10、13、6
tail[1] = 3、IS length = 2：、5、、7、11 、8、10、13、6
tail[2] = 6、IS length = 3：、5、、7、11、8、10、13、~6
tail[3] = 8、IS length = 4：、5、、、11、、10、13、6
tail[4] = 10、IS length = 5：、5、,,11,,、13、6
tail[5] = 13、IS length = 6：、5、、、11、、、、6

このプレゼンテーションは、あなたが可能バイナリ検索（tailの定義された部分は常にソートされています）を使用してtailを更新し、アルゴリズムの最後に結果を検索します。

Answer 2

テールは最長増加サブシーケンス（LIS）を検出します。

あなたが提供し、理解していると主張されているリンクに記載されている説明に従って、それ自体が更新されます。例を確認してください。

最初のifステートメントを説明するテールの最初の要素に最小値を設定します。

2番目のif文は、LISがその長さを最大にしたいので、それが大きくなるようにします。