最长的子序列，其元素构成一组递增整数

查找数组中最长的连续子序列的长度，其中的元素构成一组连续增加的整数。输入文件包含数字n（数组中的元素数），后跟整数n。
示例输入 - 10 1 6 4 5 2 3 8 10 7 7
示例输出-6（1 6 4 5 2 3，因为它们使集合1 2 3 4 5 6）。
我能够编写满足0<n<5000的算法，但为了获得100个点，该算法必须为0<=n<=50000工作。最长的子序列，其元素构成一组递增整数

来源

2017-04-14 David Asryan

或许，如果你发布一些代码来显示你已经尝试了什么，人们可能没有解决这一问题。（虽然，因为你要求更高效的算法，所以我不是你可以提供的技术比你已经拥有的更多...） –

这样的事情呢？按降序排列数组元素，每个元素以其索引范围作为局部最大值（例如，A[0] = 10应该是数组索引的最大值，[0, 10]，而A[3] = 4应该是数组索引的局部最大值，[3,3]。现在遍历此列表，找到最长，连续下降的序列，其中的指数范围都包含在初始范围。

10 1 6 4 5 2 3 8 10 7 7 
=> 10, [ 0,10] 
    8, [ 1, 7] 
    7, [ 9,10] 
    6, [ 1, 6] <-- 
    5, [ 3, 6] | ranges 
    4, [ 3, 3] | all 
    3, [ 5, 6] | contained 
    2, [ 5, 5] | in [1,6] 
    1, [ 1, 1] <--

来源

2017-04-17 04:39:29

嗯，确实是一个非常好的解决方案，但有反复出现的元素确实伤害了算法rithm。例如，如果在5到达另一个5之后，算法会变得非常模糊。或者在更坏的情况下，如果数组是这样的 - 1 5 4 2 3 7 1 5 4 2 3？ –

@DavidAsryan感谢您的评论。按照其开始索引排列数组中的每组重复项。任何作为连续任期候选人的副本都是（1）该条款之后的下一个较低的数字，以及（2）由于是下一个较低的数字，必须共享相同的开始和结束（如果他们在同一侧）或者具有相互排斥的索引范围作为局部最大值（例如，在你的例子中，5的值作为连续7的候选项，例如'1 5 4 2 3 7 1 5 4 2 3'）。 –

@DavidAsryan你也可以澄清一下这样的解决方案：'1 1 2 2 3 3 4 4'。 –

最长的子序列，其元素构成一组递增整数

回答

相关问题