NlogN 中最长增加的子序列长度.[理解算法]

Question

>问题陈述：目标是找到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。

所以我想了解尾巴中存储了什么？这将有助于我理解这个算法的正确性。

Answer 1

tail[i]是长度i+1递增子序列(IS)的最小结束值。

这就是为什么tail[0]是"最小值"，以及为什么当当前值大于当前最长序列的结束值时，我们可以增加LIS(length++)的值。

假设您的示例是输入的起始值：

输入 = 2， 5， 3， 7， 11， 8， 10， 13， 6， ...

经过我们算法的9步骤tail看起来像这样：
tail = 2， 3， 6， 8， 10， 13， ...

tail[2]是什么意思？这意味着长度3的最佳 IS 以tail[2]结尾。我们可以构建一个长度的 IS，4用大于tail[2]的数字扩展它。

tail[0] = 2，IS length = 1：2， 5， 3， 7， 11， 8， 10， 13， 6tail[1] = 3，IS length = 2：2， 5， 3， 7， 11， 8， 10， 13， 6tail[2] = 6，IS length = 3

：2， 5， 3， 7， 11， 8， 10，13， 6tail[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， 6tail[5] = 13，IS length = 6：2， 5，3，7， 11，8，10，13， 6

此演示文稿允许您使用二叉搜索(请注意，tail的已定义部分始终排序)来更新tail并在算法结束时查找结果。

Answer 2

尾部旋转最长递增子序列 (LIS)。

它将按照您提供并声称已理解的链接中给出的解释进行自我更新。检查示例。

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

第二个 if 语句允许 LIS 增长，因为我们希望最大化其长度。