Finding maximum size of range in a sorted integer array

One possible solution would be to iterate the array, keeping the the current range as long as the numbers are successors. If the next number is not a successor of the previous number, close the current range and store its length - by comparing it to the length of the last range.

In this approach, the array is iterated only once and the maximum found length of a range is updated in constant time, yielding an O(n) algorithm where n is the number of elements in the input.

An implementation in C#-like pseudocode could be as follows.

int MaximumLength = minus infinity
int CurrentValue = Input[0];
int CurrentLength = 1;

for(int i = 1; i < Input.Length; i++)
{
    if ( CurrentValue + 1 == Input[i] )
    {
        // same range
        CurrentLength = CurrentLength + 1;
    }
    else
    {
        // new range
        MaximumLength = Math.Max(MaximumLength, CurrentLength);
        CurrentLength = 1;
    }
    CurrentValue = Input[i];
}
// check current length again after loop termination
MaximumLength = Math.Max(MaximumLength, CurrentLength);

It is impossible to obtain better than O(n) because the input cannot be read in less than O(n) time. If that would be possible, it would imply that there are instances for which the result does not depend on every element of the input, which is not the case for the given problem. The algorithm Philipp Maurer has sketched below would also yield an O(n) runtime bound if the maximum range length is 1, i.e. no adjacent numbers in the input are successors.

Something like this should find the maximum length first and not last.

Let max = 0
Let n = array length
While n > 2
  Let m = 0
  While m <= (array length - n)
    Let first = m
    Let last = m + n - 1 
    Let diff = (value of element 'last' in array) - (value of element 'first' in array)
    if diff = n - 1 then
      max = n
      stop
    end if
    Increase m
  end while
  Decrease n
end while

Edit (javascript implementation)

var a = [1,2,5,9,10,12,20,21,22,23,24,26,27];
var max = 1;
var n = a.length;
while(n > 2) {
  var m = 0;
  while(m <= a.length - n)
  {
    var first = m;
    var last = m + n - 1;
    var diff = a[last] - a[first];
    if (diff == n - 1 && diff > max) {
      max = n;
      break;
    }
    m++;
    }
  n--;
}

console.log(max);

JSFiddle

I think looping and comparing with stored previous maximum length is optimal solution. Maybe like this:

function findLongestRange(input) {
  let maxLength = 0
  let currentLength = 0

  for (let i = 0; i < input.length; i++) {
    if (i !== input.length) {
      if (input[i] === input[i + 1] - 1) {
        currentLength++
      } else {
        if (maxLength <= currentLength && currentLength !== 0) {
          maxLength = currentLength + 1
        }
        currentLength = 0
      }
    }
  }

  return maxLength
}

const data = [1, 2, 5, 9, 10, 12, 20, 21, 22, 23, 24, 26, 27]
console.log(findLongestRange(data))

Here is the version with tests to check how it works with different input.

const data = [1, 2, 5, 9, 10, 12, 20, 21, 22, 23, 24, 26, 27]

function findLongestRange(input) {
  let maxLength = 0
  let currentLength = 0

  for (let i = 0; i < input.length; i++) {
    if (i !== input.length) {
      if (input[i] === input[i + 1] - 1) {
        currentLength++
      } else {
        if (maxLength <= currentLength && currentLength !== 0) {
          maxLength = currentLength + 1
        }
        currentLength = 0
      }
    }
  }

  return maxLength
}

console.clear()
;[
  [[1,2,5,6,7,1,2], 3],
  [[], 0],
  [data, 5],
  [[1,2,3], 3],
  [[1,3,4,6,8,1], 2],
  [[1,3,5], 0],
].forEach((test, index) => {
  const result = findLongestRange(test[0])
  console.assert(result === test[1], `Fail #${index}: Exp: ${test[1]}, got ${result}`)
})

A Python answer:

l = [1,2,5,9,10,12,20,21,22,23,24,26,27]
current_range = None
current_range_val = 0
max_range = 0
max_range_val = 0
for i, j in zip(l, l[1:]):
    if j - i == 1:
        current_range_val += 1
        if current_range is None:
            current_range = (i, j)
        current_range = (current_range[0], j)
    else:
        if current_range_val > max_range_val:
            max_range = current_range
            max_range_val = current_range_val
        current_range_val = 0
        current_range = (j, None)

print(max_range)

gives

(20, 24)