给定一个未排序的正整数数组，求排序后元素连续的最长子数组的长度。你能想到一个 O(n) 的解决方案吗？
例子：
{10, 5, 3, 1, 4, 2, 8, 7}，答案是 5。
{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} 是结果子数组。
我可以想到一种方法，对于每个子数组，检查 (maximum - minimum + 1) 是否等于该子数组的长度，如果为真，则它是一个连续子数组。取最长的。但它是 O(n^2) 并且不能处理重复。
有人可以提供更好的方法吗？
解决 O(n) 中没有重复的原始问题的算法。也许，它可以帮助某人开发处理重复的 O(n) 解决方案。
输入：[a1, a2, a3, ...]
将原始数组映射为对，其中第一个元素是一个值，第二个元素是数组的索引。
数组：[[a1, i1], [a2, i2], [a3, i3], ...]
使用一些 O(n) 算法（例如计数排序）对这个对数组进行排序，以便按值进行整数排序。我们得到另一个数组：
数组：[[a3, i3], [a2, i2], [a1, i1], ...]
其中 a3, a2, a1, ... 按排序顺序排列。
通过对的排序数组运行循环
在线性时间内，我们可以检测到连续的数字组 a3、a2、a1。连续的组定义是下一个值 = 上一个值 + 1。在该扫描期间，保持当前组大小 ( n )、索引的最小值 ( min ) 和索引的当前总和 ( actualSum )。
在连续组内的每个步骤上，我们可以估计索引的总和，因为它们创建了具有第一个元素min、 step 1和到目前为止看到的组大小n的算术级数。这个总和估计可以使用算术级数公式在 O(1) 时间内完成：
估计总和 = (a1 + an) * n / 2;
估计总和 = (min + min + (n - 1)) * n / 2;
估计总和 = min * n + n * (n - 1) / 2；
如果在连续组内的某个循环步骤上估计总和等于实际总和，则到目前为止看到的连续组满足条件。将n保存为当前最大值结果，或在当前最大值和n之间选择最大值。
如果在值元素上我们不再看到连续组，则重置所有值并执行相同操作。
这将需要对数据进行两次传递。首先创建一个哈希映射，将整数映射到布尔值。我更新了我的算法以不使用来自 STL 的地图，我很肯定它在内部使用排序。该算法使用散列，并且可以轻松更新任何最大或最小组合，甚至可能是整数可以获得的所有可能值。
#include <iostream>
using namespace std;
const int MINIMUM = 0;
const int MAXIMUM = 100;
const unsigned int ARRAY_SIZE = MAXIMUM - MINIMUM;
int main() {
bool* hashOfIntegers = new bool[ARRAY_SIZE];
//const int someArrayOfIntegers[] = {10, 9, 8, 6, 5, 3, 1, 4, 2, 8, 7};
//const int someArrayOfIntegers[] = {10, 6, 5, 3, 1, 4, 2, 8, 7};
const int someArrayOfIntegers[] = {-2, -3, 8, 6, 12, 14, 4, 0, 16, 18, 20};
const int SIZE_OF_ARRAY = 11;
//Initialize hashOfIntegers values to false, probably unnecessary but good practice.
for(unsigned int i = 0; i < ARRAY_SIZE; i++) {
hashOfIntegers[i] = false;
}
//Chage appropriate values to true.
for(int i = 0; i < SIZE_OF_ARRAY; i++) {
//We subtract the MINIMUM value to normalize the MINIMUM value to a zero index for negative numbers.
hashOfIntegers[someArrayOfIntegers[i] - MINIMUM] = true;
}
int sequence = 0;
int maxSequence = 0;
//Find the maximum sequence in the values
for(unsigned int i = 0; i < ARRAY_SIZE; i++) {
if(hashOfIntegers[i]) sequence++;
else sequence = 0;
if(sequence > maxSequence) maxSequence = sequence;
}
cout << "MAX SEQUENCE: " << maxSequence << endl;
return 0;
}
基本思想是将哈希映射用作桶排序，这样您只需对数据进行两次传递。这个算法是 O(2n)，而这又是 O(n)
在它的数学集合定义中查看数组S ：
S = U j = 0 k (我j )
其中I j是不相交的整数段。您可以设计一个特定的区间树（基于您喜欢的红黑树或自平衡树:)）以将数组存储在此数学定义中。节点和树结构应如下所示：
struct node {
int d, u;
int count;
struct node *n_left, *n_right;
}
这里，d 是整数段的下界，u 是上界。添加以处理数组中可能的重复项：当尝试在树中插入一个已经存在的元素时，我们将增加找到它的节点count的值，而不是什么都不做。count
struct root {
struct node *root;
}
树只会存储不相交的节点，因此，插入比经典的红黑树插入要复杂一些。插入间隔时，您必须扫描现有间隔的潜在溢出。在您的情况下，由于您只会插入单例，因此不应增加太多开销。
给定三个节点 P、L 和 R，L 是 P 的左孩子，R 是 P 的右孩子。然后，您必须强制 Lu < Pd 和 Pu < Rd（当然，对于每个节点，d <= u） .
插入整数段 [x,y] 时，必须找到“重叠”段，即满足以下不等式之一的区间 [u,d]：
y >= d - 1
或
x <= u + 1
如果插入的区间是单例x，那么您最多只能找到 2 个重叠区间节点 N1 和 N2 使得N1.d == x + 1和N2.u == x - 1。然后你必须合并这两个区间并更新计数，这样你就可以得到 N3 N3.d = N2.d，N3.u = N1.u和N3.count = N1.count + N2.count + 1。由于 和 之间N1.d的N2.u增量是两个分段不相交的最小增量，因此您必须具有以下条件之一：
所以插入仍然会在O(log(n))最坏的情况下。
从这里开始，我无法弄清楚如何处理初始序列中的顺序，但这里有一个可能很有趣的结果：如果输入数组定义了一个完美的整数段，那么树只有一个节点。
UPD2：以下解决方案是针对不需要子数组连续的问题。我误解了问题陈述。不删除这个，因为有人可能有一个基于我的想法，可以解决实际问题。
这是我想出的：
创建一个字典的实例（它被实现为哈希表，在正常情况下给出 O(1)）。键是整数，值是整数的哈希集（也是 O(1)） - var D = new Dictionary<int, HashSet<int>>。
遍历数组A并为每个n带有索引的整数i做：
n-1和n+1是否包含在D.
D.Add(n, new HashSet<int>)n-1，做D.Add(n, D[n-1])D[n-1].UnionWith(D[n+1]); D[n+1] = D[n] = D[n-1];D[n].Add(n)现在遍历每个键D并找到具有最大长度的哈希集（查找长度为 O(1)）。最大的长度将是答案。
据我了解，最坏情况的复杂性将是 O(n*log(n))，这仅仅是因为UnionWith操作。我不知道如何计算平均复杂度，但它应该接近 O(n)。如果我错了，请纠正我。
UPD：要说代码，这是 C# 中的测试实现，它在 OP 的两个示例中都给出了正确的结果：
var A = new int[] {4, 5, 1, 5, 7, 6, 8, 4, 1};
var D = new Dictionary<int, HashSet<int>>();
foreach(int n in A)
{
if(D.ContainsKey(n-1) && D.ContainsKey(n+1))
{
D[n-1].UnionWith(D[n+1]);
D[n+1] = D[n] = D[n-1];
}
else if(D.ContainsKey(n-1))
{
D[n] = D[n-1];
}
else if(D.ContainsKey(n+1))
{
D[n] = D[n+1];
}
else if(!D.ContainsKey(n))
{
D.Add(n, new HashSet<int>());
}
D[n].Add(n);
}
int result = int.MinValue;
foreach(HashSet<int> H in D.Values)
{
if(H.Count > result)
{
result = H.Count;
}
}
Console.WriteLine(result);
不要抱太大希望，这只是部分答案。
我很有信心这个问题在O(n). 不幸的是，我无法证明这一点。
如果有办法在小于的时间内解决它O(n^2)，我怀疑该解决方案基于以下策略：
O(n)（或者可能O(n log n)）是否存在一个连续的子数组，正如你用至少i元素描述的那样。让我们称之为谓词E(i)。i使用二分法来找到E(i)保持的最大值。该算法的总运行时间将是O(n log n)（或O(n log^2 n)）。
这是我能想出的将问题简化为另一个问题的唯一方法，该问题至少有可能比原始公式更简单。但是，我找不到E(i)在小于的时间内计算的方法O(n^2)，所以我可能完全离开了......
这是考虑问题的另一种方式：假设您有一个仅由 1 和 0 组成的数组，您想找到最长连续运行的 1。这可以通过对 1 进行游程编码（忽略 0）在线性时间内完成。为了将您的原始问题转换为这个新的运行长度编码问题，您需要计算一个新数组 b[i] = (a[i] < a[i+1])。这不必显式地完成，您可以隐式地完成它以实现具有恒定内存需求和线性复杂度的算法。
第一个O(nlog(n))在时间和O(n)空间上，第二个O(n)在时间和O(n)空间上，第三个O(n)在时间和O(1)空间上。