代码之家 › 专栏 › 技术社区 › somerandomguy

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

correctness binary-search sorting algorithm

somerandomguy · 技术社区 · 6 年前

问题陈述:目标是在非连接时序中找到最长的递增子序列(不连续)。

算法:我理解这里解释的算法: 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。但尾巴将储存2,3,6,8,10,13。

所以我想知道尾巴里储存了什么?。这将帮助我理解这个算法的正确性。

2 回复 | 直到 6 年前

DAle 6 年前

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

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

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

输入=2,5,3,7,11,8,10,13,6。。。

之后 9 我们算法的步骤 tail 如下所示:
尾部=2,3,6,8,10,13。。。

什么是 tail[2] 方法这意味着最好的是长度 3 以结尾 尾部[2] . 我们可以建立一个长度为 4 用大于的数字进行扩展 尾部[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.

本演示允许您使用二进制搜索(请注意 尾 始终排序)以更新 尾 并在算法末尾找到结果。

gsamaras 6 年前

尾序列是最长的增长子序列(LIS)。

它将根据您提供并声称理解的链接中给出的解释进行更新。检查示例。

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

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

推荐文章

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Laveen · python中的二进制搜索程序不会停止循环

7 年前

MEnnabah · 高效实现二进制搜索

7 年前

Tanay Choudhary · 如何为这个二进制搜索函数创建具有修改的最大/最小值的新数组

7 年前

user8742308 · 如果指定的数字位于排序数组的末尾或开头,则二进制搜索函数无法找到它们

7 年前

James Chavez · 二进制搜索查找不重复java的元素

7 年前

yrrah2 · 为什么我的二进制搜索使用这么多比较?

7 年前

James · 阻塞问题的一种算法设计[C++代码]

7 年前

Artemis · 为什么在二进制搜索中我们要除以2而不是其他更高的常数

7 年前

Johnny · 二进制搜索是贪婪算法吗?

7 年前