元素构成连续序列的最长子阵列

Question

{4,5,1,5,7,6,8,4,1}，答案是5。

对于第一个例子，子数组{5,3,1,4,2}排序后可以形成连续序列1,2,3,4,5，它们是最长的。

对于第二个示例，子数组{5,7,6,8,4}是结果子数组。

Answer 1

在O(n)中无重复项解原问题的算法。也许，它有助于某人开发处理重复项的O(n)解决方案。

投入:[a1、a2、a3、...]

将原始数组映射为对，其中第一个元素是值，第二个元素是数组的索引。

在排序的对数组中运行循环

在线性时间内，我们可以检测到连续的数组a3、a2、A1。连续组定义为next值=prev值+1。在扫描期间，保持当前组大小(n)、索引的最小值（min）和当前索引的总和（actualSum）。

在连续群内的每一步上，我们可以估计指数的和，因为它们用第一个元素min，步骤1，和到目前为止看到的群的大小n创建算术级数。这个和估计可以用算术级数的公式在O(1)时间内完成：

估计和=min*n+n*(n-1)/2；

如果在连续组内的某一循环步骤上估计和等于实际和，则可见到目前为止连续组满足条件。将n保存为当前最大值结果，或在当前最大值和n之间选择最大值。

如果在值元素上我们不再看到连续组，那么重置所有值并执行相同的操作。