我一直在处理一个问题：
查找数组中最大的一组连续数字。
假设我们有一个数组[5, 43, 4, 56, 3, 2, 44, 57, 58, 1]，这个数组中最大的一组连续数字是5（1、2、3、4和5）。
求解算法必须是O（n）的时间复杂度。
我已经用下面的ruby代码解决了这个问题，但我在根据解决方案的需要将它移植到PHP时遇到了问题。
arr = [8, 13, 14, 10, 6, 7, 8, 14, 5, 3, 5, 2, 6, 7, 4]
result = []
stage = []
for i in arr:
if len(stage) > 0 and i != stage[-1]+1:
if len(stage) > 1:
result.append(stage)
stage = []
stage.append(i)
print result
$a = [8, 13, 14, 10, 6, 7, 8, 14, 5, 3, 5, 2, 6, 7, 4];
$res = [];
$stage = [];
foreach($a as $i) {
if(count($stage) > 0 && $i != $stage[count($stage)-1]+1) {
if(count($stage) > 1) {
$res[] = $stage;
}
$stage = [];
}
$stage[] = $i;
}
print_r($res);
不是O（n），但你可以试试这个：
// Define array
$array = array(5,8,3,2,10,11,15,13,12,1,4,5,16);
// Sorting
asort($array);
$previous = null;
$result = array();
$consecutiveArray = array();
// Slice array by consecutive sequences
foreach($array as $number) {
if ($number == $previous + 1) {
$consecutiveArray[] = $number;
} else {
$result[] = $consecutiveArray;
$consecutiveArray = array($number);
}
$previous = $number;
}
$result[] = $consecutiveArray;
// Get length of each sub array
$count = array_map('count', $result);
您可以通过max($count)获得最大长度。
此解决方案为您提供以下阵列：
array(
0 => array(1,2,3,4,5)
1 => array(5)
2 => array(8)
3 => array(10,11,12,13)
4 => array(15,16)
这里有一个python（我的PHP不太好），如果你的序列在减少，它会按照你的描述要求执行：
lists = dict()
for i in val:
if i in lists:
continue
a = {i}
if (i + 1) in lists:
b = lists[i+1]
b.update(a)
a = b
if (i - 1) in lists:
b = lists[i-1]
# this messes up the complexity
for k in b:
lists[k] = a
a.update(b)
lists[i] = a
其思想是lists维护一个集合的dict，该集合索引在列表中的所有元素上。每当遇到新元素时，上一个集合和下一个集合都会合并（如果存在）。
update操作在技术上是o(n)，但它不由外部循环复合，因为只有n才能通过合并插入到集合中。整体为o(n)
如果序列没有排序，+1和-1集合的合并会产生不太好的复杂性。