NlogN 中最长的递增子序列长度。[了解算法]

Question

问题陈述：目标是在 nlogn 时间内找到最长的递增子序列（不连续）。

算法：我理解这里解释的算法： http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/.

我不明白的是在下面的代码中 tail 中存储了什么。

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。但是 tail 将存储 2,3,6,8,10,13.

所以我想了解 tail 中存储了什么？这将帮助我理解该算法的正确性。

Answer 1

Tail srotes 最长递增子序列 (LIS)。

它将根据您提供并声称已理解的 link 中的解释自行更新。检查示例。

您想要尾部第一个元素的最小值，这解释了第一个 if 语句。

第二个 if 语句允许 LIS 增长，因为我们想要最大化它的长度。

Answer 2

tail[i]是长度为i+1的递增子序列（IS）的最小终值。

这就是为什么tail[0]是'smallest value'以及为什么当当前值大于当前最长序列的结束值时我们可以增加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 的 IS，用大于 tail[2] 的数字扩展它。

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

本演示文稿允许您使用二进制搜索（注意 tail 的定义部分始终排序）来更新 tail 并在算法结束时查找结果。

NlogN 中最长的递增子序列长度。[了解算法]

Longest Increasing subsequence length in NlogN.[Understanding the Algo]

sorting

algorithm

correctness

binary-search