Program to find the longest sequence in an array

This post will teach you to find the longest sequence of elements in an array. We need two sets in this program. One for adding the current elements and one which contains the longest sequence of elements.The logic is as follows:-

• Initialize current set and set containing longest sequence of values.
• For each current element, we will check the next elements.
• Clear the values in current set.
• Add the current element to a set.
• Assign previous element to current element
• If the next element is 1 greater than the previous element, update previous element as the next element and next element as next element of array.
• Else check whether the size of current set is greater than the set which contain longest sequence of elements.
• If it is greater, then remove all the elements form longest sequence set and add all elements of current sequence set to that.

Since we need to loop all the elements twice, the time complexity of the program is O(n^2). The program is as follows:

import java.util.LinkedHashSet;

import java.util.Set;

public class longestSequence {

public static void main(String args[])

{

int arr[] ={1,2,6,3,4,5,1,2,3,7,8,13,14,15,16,23,1,4,6,7,9};

Set<Integer> mSet = new LinkedHashSet<Integer>();

mSet = longSequence(arr);

System.out.println(" The longest sequence is as follows");

for(Integer elem: mSet)

{

System.out.print(elem+"  ");

}

}

public static Set<Integer> longSequence(int arr[])

{

Set<Integer> returnSet = new LinkedHashSet<Integer>();

Set<Integer> storeSet = new LinkedHashSet<Integer>();

int length=arr.length;

for(int i=0;i<length;i++)

{   

storeSet.clear();

storeSet.add(arr[i]);

int prev=arr[i];

for(int j=i+1;j<length;j++)

{

if(arr[j]==prev+1)

{

storeSet.add(arr[j]);

prev=arr[j];

}

else

{  

if(storeSet.size()>returnSet.size())

{   

returnSet.clear();

returnSet.addAll(storeSet);

}

break;

}

}

}

return returnSet;

}

}

Thank you for reading. Please comment if you have any doubts. All queries will be responded within one day.