由于正整数的无序排列，找到最长的子数组的元素进行排序时，有连续的长度。你能想到的一个O（n）的解决方案？

Given an unsorted array of positive integers, find the length of the longest subarray whose elements when sorted are continuous. Can you think of an O(n) solution?

例如：

{10，5,3，1,4，2,8，7}，答案为5

{10, 5, 3, 1, 4, 2, 8, 7}, answer is 5.

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

{4, 5, 1, 5, 7, 6, 8, 4, 1}, answer is 5.

有关的第一个例子，子阵列{5,3，1，4,2}排序时能形成连续的序列1,2,3,4,5，是最长的。

For the first example, the subarray {5, 3, 1, 4, 2} when sorted can form a continuous sequence 1,2,3,4,5, which are the longest.

有关的第二个例子中，子阵列{5,7，6，8，4}是结果子阵列

For the second example, the subarray {5, 7, 6, 8, 4} is the result subarray.

我能想到的方法，这对于每个子阵列，检查（最大值 - 最小值+ 1）的等于该子数组的长度，如果是真的，那么它是一个连续的子阵。就拿最久的。但它是O（n ^ 2），并不能处理重复。

I can think of a method which for each subarray, check if (maximum - minimum + 1) equals the length of that subarray, if true, then it is a continuous subarray. Take the longest of all. But it is O(n^2) and can not deal with duplicates.

有人可以给出一个更好的方法？

Can someone gives a better method?

推荐答案

算法来解决原来的问题，为O（n）的没有重复。也许，这可以帮助别人发展为O（n）解决方案，以重复处理。

Algorithm to solve original problem in O(n) without duplicates. Maybe, it helps someone to develop O(n) solution that deals with duplicates.

输入：[A1，A2，A3，...]

Input: [a1, a2, a3, ...]

地图原始数组作为对，其中第一个元素是一个值，而第二个是数组的索引。

Map original array as pair where 1st element is a value, and 2nd is index of array.

阵列：[[A1，I1]，[A2，12]，[A3，i3的]，...]

Array: [[a1, i1], [a2, i2], [a3, i3], ...]

通过值排序该数组对一些O（n）的算法（如计数排序）为整数排序的 的。 我们得到一些其他数组：

Sort this array of pairs with some O(n) algorithm (e.g Counting Sort) for integer sorting by value. We get some another array:

阵列：[[A3，i3的]，[A2，12]，[A 1，I1]，...]

Array: [[a3, i3], [a2, i2], [a1, i1], ...]

，其中A3，A2，A1，......都在有序。

where a3, a2, a1, ... are in sorted order.

通过对数组排序的运行循环

Run loop through sorted array of pairs

在线性时间，我们可以检测到连续的组号A3，A2，A1。一组连续的定义是下一个值= preV值+ 1。 在此期间，扫描保持当前组大小（ N ），指数的最低值（分），和​​指数的当前和（ actualSum ）

In linear time we can detect consecutive groups of numbers a3, a2, a1. Consecutive group definition is next value = prev value + 1. During that scan keep current group size (n), minimum value of index (min), and current sum of indices (actualSum).

在每个步骤内连续组中，我们可以估算指标的总和，因为他们创建的第一个元素等差数列的分，步 1 ，然后组大小见过这么远 N 。 这笔款项估计可以在O完成（1）用公式等差时间：

On each step inside consecutive group we can estimate sum of indices, because they create arithmetic progression with first element min, step 1, and size of group seen so far n. This sum estimate can be done in O(1) time using formula for arithmetic progression:

估计金额=（A1 +的）* N / 2;

estimate sum = (a1 + an) * n / 2;

估计金额=（分钟+分+（N - 1））* N / 2;

estimate sum = (min + min + (n - 1)) * n / 2;

估计金额=分钟* N + N *（N - 1）/ 2;

estimate sum = min * n + n * (n - 1) / 2;

如果在里面的一组连续的估计和的几个循环步骤等于实际的总和，那么迄今为止看到一组连续满足的条件。保存的 N 作为当前最大的结果，或者选择当前最大值之间最大的 N

If on some loop step inside consecutive group estimate sum equals to actual sum, then seen so far consecutive group satisfy the conditions. Save n as current maximum result, or choose maximum between current maximum and n.

如果对价值的元素，我们再看到连续的组，然后重置所有的值，做同样的。

If on value elements we stop seeing consecutive group, then reset all values and do the same.

code例如： https://gist.github.com/mishadoff/5371821