最长的非递减序列 - n log n？

我想了解n log n解决方案。看起来你不需要在任何给定的点上存储整个临时列表，而只需要最后一个元素。最长的非递减序列 - n log n？

这是如何工作的？

我不想发布在现有的职位，所以创建了一个新的。

花了很多时间去理解它。。。:(

来源

2014-08-30 ND27

你可以发布你所指的解决方案吗？ – amey91 2014-08-30 20:37:39

你没有对整个临时名单储存在任何给定的点做什么，只是最后一个元素会做

首先，回顾一下为O（n ）的解决方案：在设置有在每个元件i的长度的阵列L最长非递减的A在元件i结束序列下面是一个例子：

A: 2 5 7 3 8 2 9 6 9 
L: 1 2 3 2 4 2 5 3 6

现在想象一下设置一个数组M，它在每个索引k存储A的元素，该元素结束长度为k的最长非递减子序列。下面是如何M会看每个步骤（破折号-显示了未填充的地方）

M (step 0) - - - - - - - - - 
M (step 1) 2 - - - - - - - - 
M (step 2) 2 5 - - - - - - - 
M (step 3) 2 5 7 - - - - - - 
M (step 4) 2 3 7 - - - - - - 
M (step 5) 2 3 7 8 - - - - - 
M (step 6) 2 2 7 8 - - - - - 
M (step 7) 2 2 7 8 9 - - - - 
M (step 8) 2 2 6 8 9 - - - - 
M (step 9) 2 2 6 8 9 9 - - -

通过示例工作手动理解填写阵列M的机制。

现在关键观察：在每一步，M是按非递减顺序排列。直观地说，这很明显，因为否则可以将较大的数字连接到较长的序列，并向上移动数组M。

这可以让你建立你的算法：

商店当你A[i]到达已填写
的最后一个位置的MmaxPos，在M[0..maxPos]换一个地方运行的二进制搜索，其中A[i]应被放置
如果你最终在阵列的中间，用旧的值替换min(A[i], oldValue)
如果元素大t汉或等于加到M到目前为止，添加A[i]到结束，并递增所有元素maxPos

这是很容易看到的是，以上算法是O（n *的log（n）），因为每一个其n步骤使用二进制搜索，即log（n）。

来源

2014-08-30 20:43:38 dasblinkenlight

太棒了。只是，如果我们最终排在阵列中间，我们并不需要替换旧值，是吗？ – R2B2 2014-08-30 20:52:39

@ user3923424你是对的，我们不需要总是替换值;只有在更换更小的时候。我编辑了答案，使用'min'函数来表明这一点。 – dasblinkenlight 2014-08-30 22:08:59

最长的非递减序列 - n log n？

回答

相关问题