# Java Program to Find longest consecutive subsequence

## Longest Consecutive subsequence in Java

Here, in this page we will discuss the program to find the longest consecutive subsequence in C++ . We are Given with an array of integers, we need to find the length of the longest sub-sequence such that elements in the sub-sequence are consecutive integers, the consecutive numbers can be in any order.

## Method Discussed :

• Method 1 : Brute Force
• Method 2 : Using Hash-map
• Method 3 : Using Priority Queue.

## Method 1 (Brute force Approach) :

• First sort the given input array.
• Remove the multiple occurrences of elements, run a loop and keep a count and max (both initially zero).
• Run a loop from 0 to N and if the current element is not equal to the previous (element+1) then set the count to 1 else increase the count.
• Update max with a maximum of count and max.
Run
```import java.io.*;
import java.util.*;
public
class Main {
static int findLongestConseqSubseq(int arr[], int n)
{

// Sort the array
Arrays.sort(arr);

int ans = 0, count = 0;

ArrayList v = new ArrayList();

// Insert repeated elements
// only once in the vector
for (int i = 1; i < n; i++)
{
if (arr[i] != arr[i - 1])
}

// Find the maximum length
// by traversing the array
for (int i = 0; i < v.size(); i++)
{

// Check if the current element is
// equal to previous element +1
if (i > 0 && v.get(i) == v.get(i - 1))
count++;
else
count = 1;

// Update the maximum
ans = Math.max(ans, count);
}
return ans;
}

// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 9, 3, 10, 4, 20, 2 };
int n = arr.length;

System.out.println(
"Length of the Longest "
+ "contiguous subsequence is "
+ findLongestConseqSubseq(arr, n));
}
}```

### Output :

`Length of the Longest contiguous subsequence is 3`

## Method 2 :

• First we will create a hash-map.
• Now, iterate over the array for every i-th element check if this element is the starting point of a subsequence. To check this, simply look for arr[i] – 1 in the hash, if not found, then this is the first element a subsequence.
• If this element is the first element, then count the number of elements in the consecutive starting with this element. Iterate from arr[i] + 1 till the last element that can be found.
• If the count is more than the previous longest subsequence found, then update this.
Run
```import java.io.*;
import java.util.*;
class Main {
// consecutive subsequence
static int findLongestConseqSubseq(int arr[], int n)
{

HashSet S = new HashSet();
int ans = 0;

// Hash all the array elements
for (int i = 0; i < n; ++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.contains(arr[i] - 1))
{
// Then check for next elements
// in the sequence
int j = arr[i];
while (S.contains(j))
j++;

// update  optimal length if this
// length is more
if (ans < j - arr[i])
ans = j - arr[i];
}
}
return ans;
}

// Driver Code
public static void main(String args[])

{

int arr[] = { 1, 9, 3, 10, 4, 20, 2 };
int n = arr.length;
System.out.println(
"Length of the Longest consecutive subsequence is "
+ findLongestConseqSubseq(arr, n));
}
}
```

### Output :

```Length of the Longest consecutive subsequence is 4
```

## Method 3 :

In this method we will use priority queue.

• Create a Priority Queue to store the element
• Store the first element in a variable.
• Remove it from the Priority Queue.
• Check the difference between this removed first element and the new peek element
• If the difference is equal to 1 increase count by 1 and repeats step 2 and step 3
• If the difference is greater than 1 set counter to 1 and repeat step 2 and step 3
• if the difference is equal to 0 repeat step 2 and 3
• if counter greater than the previous maximum then store counter to maximum
• Continue step 4 to 7 until we reach the end of the Priority Queue
• Return the maximum value

Run
```import java.io.*;
import java.util.PriorityQueue;
class Main {
static int findLongestConseqSubseq(int arr[], int N)
{

PriorityQueue<Integer> pq
= new PriorityQueue();
for (int i = 0; i < N; i++)
{
// array to PriorityQueue
}

// Storing the first element
// of the Priority Queue
// This first element is also
// the smallest element
int prev = pq.poll();

// Taking a counter variable with value 1
int c = 1;

// Storing value of max as 1
// as there will always be
// one element
int max = 1;

for (int i = 1; i < N; i++)
{
// check if current peek
// element minus previous
// element is greater then
// 1 This is done because
// if it's greater than 1
// then the sequence
// doesn't start or is broken here
if (pq.peek() - prev > 1)
{
// Store the value of counter to 1
// As new sequence may begin
c = 1;

// Update the previous position with the
// current peek And remove it
prev = pq.poll();
}

// Check if the previous
//  element and peek are same
else if (pq.peek() - prev == 0)
{
// Update the previous position with the
// current peek And remove it
prev = pq.poll();
}
// if the difference
// between previous element and peek is 1
else
{
// Update the counter
// These are consecutive elements
c++;

// Update the previous position
//  with the current peek And remove it
prev = pq.poll();
}

// Check if current longest
// subsequence is the greatest
if (max < c)
{
// Store the current subsequence count as
// max
max = c;
}

}
return max;

}

// Driver Code
public static void main(String args[])
throws IOException
{
int arr[] = { 1, 9, 3, 10, 4, 20, 2 };
int n = arr.length;
System.out.println(
"Length of the Longest consecutive subsequence is "
+ findLongestConseqSubseq(arr, n));
}

}
```

### Output :

```Length of the Longest consecutive subsequence is 4
```