algorithm - 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[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]方法？这意味着最好的IS长度3以 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并在算法结束时找到结果。