CareerCup

Sorting Solution:
Time Complexity = O(nlogn)
Space Complexity = O(1)

HashSet Solution:
Time Complexity = O(n) (amortized)
Space Complexity = O(n)

There is a trade-off for both the solutions.
Implemented both of them below:

public class Main {

	public static void main(String[] args) {
		int[] array = { 1, 94, 93, 1000, 2, 92, 1001};
		System.out.println("Max continuous length = "+maxContinuousLength2(array));
	}
	
	//Using sorting.
	public static int maxContinuousLength(int[] array){
		int maxLength = 1, curLength = 1;
		Arrays.sort(array);
		int prev = array[0];
		for(int i=1; i<array.length; i++){
			if(prev == array[i]-1){
				curLength++;
			}else{
				maxLength = max(maxLength,curLength);
				curLength = 1;
			}
			prev = array[i];
		}
		return maxLength;
	}
	
	//using HashSet
	public static int maxContinuousLength2(int[] array){
		int maxLength = 0;
		HashSet<Integer> set = new HashSet<Integer>();
		for(int i=0; i<array.length; i++){
			set.add(array[i]);
		}
		for(Integer i: set){
			if(!set.contains(i-1)){
				int curLength = 0;
				while(set.contains(i)){
					i++;curLength++;
				}
				maxLength = max(maxLength, curLength);
			}
		}
		return maxLength;
	}
}

O(n) solution

// Returns length of the longest contiguous subsequence
int findLongestConseqSubseq(int arr[], int n)
{
    unordered_set<int> S;
    int ans = 0;
 
    // Hash all the array elements
    for (int i = 0; i < n; i++)
        S.insert(arr[i]);
 
    // check each possible sequence from the start
    // then update optimal length
    for (int i=0; i<n; i++)
    {
        // if current element is the starting
        // element of a sequence
        if (S.find(arr[i]-1) == S.end())
        {
            // Then check for next elements in the
            // sequence
            int j = arr[i];
            while (S.find(j) != S.end())
                j++;
 
            // update  optimal length if this length
            // is more
            ans = max(ans, j - arr[i]);
        }
    }
    return ans;
}

sort the array and then look for consecutive numbers

public class Q6 {

	
	
	public static void main(String[] args) {
	

		int array[]={1,94,93,1000,2,92,1001};
		
		array=mergeSort(array);

		int last_ele=array[0];
		int i=1,count=1,max=1;
		
		
		while(i<array.length)
		{
			if(array[i]==last_ele+1)
			{
				count++;
			}
			else
			{
				if(max<count)
					max=count;
				count=1;
			}
			last_ele=array[i++];
		}
		
		System.out.println("max consecutive numbers : "+max);
		
	}

	private static int[] mergeSort(int[] array) {
		// TODO Auto-generated method stub
		
		if(array.length<=1)
			return array;
		
		int mid=array.length/2;
		
		
		int temp1[]=new int[mid];
		for(int i=0;i<mid;i++)
			temp1[i]=array[i];
		
		int temp2[]=new int[array.length-mid];
		for(int i=mid;i<array.length;i++)
			temp2[i-mid]=array[i];
		
		temp1=mergeSort(temp1);
		temp2=mergeSort(temp2);
		
		array=mergeArray(temp1, temp2);
		
		return array;
	}

	private static int[] mergeArray(int[] array1, int[] array2) {
		// TODO Auto-generated method stub
		
		int result[]=new int[array1.length+array2.length];
		
		int i=0,j=0;
		
		while(i<array1.length&&j<array2.length)
		{
				if(array1[i]<=array2[j])
				{
					result[i+j]=array1[i];
					++i;
				}
				else
				{
					result[i+j]=array2[j];
					++j;
				}
			
		}
		
		while(j<array2.length)
		{
			result[i+j]=array2[j];
			++j;
		}
		
		while(i<array1.length)
		{
			result[i+j]=array1[i];
			++i;
		}
		
		
		
		return result;
	}

}

def maxConsecutive(a):
	# a = [1, 94, 93, 1000, 2, 92, 1001]
	a.sort()
	consecutive = 0
	prev = a[0]
	m = consecutive
	for each in a[1::]:
		if each == prev + 1:
			consecutive += 1
		else:
			if consecutive != 0:
				if m < consecutive + 1:
					m = consecutive + 1
			consecutive = 0
		prev = each
	return m

O(n) solution (ignoring sorting)

int maxLenConsNums(vector<int>& arr){
    if(arr.size() <= 1) return arr.size();
    
    sort(arr.begin(), arr.end());
    int maxLen = 0, currLen = 0;
    int i = 1;
    while(i < arr.size()){
        int diff = arr[i] - arr[i-1];
        if(diff == 1){
            currLen++;
        }
        else if(diff != 1){
            maxLen = max(maxLen, currLen);
            currLen = 0;
        }
        i++;
    }
    return maxLen+1;
}

Sort the array .using Arrays.sort(aray);
find
int count=0;
for(int j=0;j<ar.length-1j++
{
if(ar[j+1]-ar[j]==1
count++;
}
SOP(count)

int maxConsecutiveNumCount(int A[], const int N)
	{
		int B[N] = {1};
		int maxCount = 0;
		
		for(int i = 1; i < N; i++)
		{
			for(int j = 0; j<i; j++)
			{
				if(A[j] == A[i]+1 || A[j] == A[i]-1)
				{
					B[i] = max(B[i], B[j]+1);
					maxCount = max(maxCount, B[i]);
				}
			}
		}
		return maxCount;
	}

int maxConsecutiveLen(vector<int>& arr){
    
    map<int,int> pos;
    
    for(int i = 0; i < arr.size(); i++){
        pos[arr[i]] = i;
    }
    
    int maxcount(0), count(0);
    
    auto p = pos.begin();
    
    for(auto i = pos.begin(); i != pos.end(); i++){
        
        if(i->first - p->first == 1){
            count++;
        }
        else{
            maxcount = max(maxcount, count);
            count = 0;
        }
        
        p = i;
    }
    
    return maxcount+1;
}

#!python3
from heapq import *

def maxConsecutive(nums):
	if not nums:
		return 0

	heap = list(nums)
	heapify(heap)

	prev = heap[0] - 1
	acc = 0
	best = 0
	for cur in popheap(heap):
		acc = (acc ÷ 1) & -int(prev + 1 == cur)
		best = max(best, acc)

#C++

#include<iostream>
using namespace std;
int main()
{
int n;int x;int ct=0;
cout<<"Enter the no of elemnts in an array";
cin>>n;
int arr[n];
for(int j=0;j<n;j++)
{
cin>>arr[j];
}
for(int i=0;i<n-1;i++)
{
x=arr[i];
if(arr[i+1]==(x+1))
{
ct++;
}
}cout<<ct;}

#include<iostream.h>
using namespace std;
int main()
{
    int n;
    int max=1;
    cin>>n;
    int temp=0;
    int arr[n];
    for(int i=0; i<n; i++)
    {
        cin>>arr[i];
    }
    for(int j=0; j<n; j++)
    {
        for(int k=j; k<n; k++)
        {
            if(arr[j]>arr[k])
            {
                temp=arr[j];
                arr[j]=arr[k];
                arr[k]=temp;
            }
        }
    }
    int x;
    for(int l=0; l<n; l++)
    {
        int ct=1;
        x=arr[l];
        for(int m=0; m<n-1; m++)
        {
            if(arr[m+1]==(x+1))
            {
                ct++;
                x=x+1;
            }
        }
        if(ct>max)
        {
            max=ct;
        }
    }
    cout<<max<<endl;
}

What about the following approach

def findMaximumNumberinJumbled(listOfNumbers):

    countyet = 1
    countMax = 1
    sortedList = sorted(listOfNumbers)
    print sortedList

    for index in range(1, len(sortedList)):
        if sortedList[index] - sortedList[index-1] != 1:
            countyet = 1
        elif sortedList[index] - sortedList[index-1] == 1:
            countyet = countyet +1
            if countyet > countMax:
                countMax = countyet

    print countMax


if __name__ == "__main__":
    findMaximumNumberinJumbled([1,94,93,1000,2,92,1001,1002,999,3,4,5,6])

sort the array and then look out in O(nlogn)