Maximum consecutive integers present in an array
Written by
Given: An array of integers, we have to find the maximum length such that the elements are consecutive integers (the consecutive numbers can be in any order).
EXAMPLES:
Input : xyz[] = {5, 54, 3, 45, 6, 92, 4};
Output : 4
The maximum consecutive elements are 3, 4, 5, 6.
Code:
#include <bits/stdc++.h>
int findlongsub(int array[], int no_of_elements)
{
std::unordered_set<int> uno_set; //taking a set of input
for (int i = 0; i < no_of_elements; i++)
uno_set.insert(array[i]);
int answer = 0;
for (int i = 0; i < no_of_elements; i++)
{
// to check for required elements in starting of set
if (uno_set.find(array[i] - 1) == uno_set.end())
{
// Checking for all the consecutive elements in set
int j = array[i];
// increment the value of array element and again search for the consecutive elements
while (uno_set.find(j) != uno_set.end())
j++;
answer = std::max(answer, j - array[i]);
}
}
return answer;
}
// Main code
int main()
{
int array[] = { 5, 54, 3, 45, 6, 92, 4 };
//here 3,4,5,6 are the longest subsequence
int no_of_elements = sizeof(array) / sizeof(int);
std::cout << findlongsub(array, no_of_elements) << std::endl;
return 0;
}
Output
4
Time complexity : O(n)