Longest Consecutive Subsequence | CPP program for the above approach ; return the length of the longest subsequence of consecutive integers ; adding element from array to PriorityQueue ; Storing the first element of the Priority Queue This first element is also the smallest element ; Taking a counter variable with value 1 ; Storing value of max as 1 as there will always be one element ; 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 ; Store the value of counter to 1 As new sequence may begin ; Update the previous position with the current peek And remove it ; Check if the previous element and peek are same ; Update the previous position with the current peek And remove it ; If the difference between previous element and peek is 1 ; Update the counter These are consecutive elements ; Update the previous position with the current peek And remove it ; Check if current longest subsequence is the greatest ; Store the current subsequence count as max ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findLongestConseqSubseq ( int arr [ ] , int N ) { priority_queue < int , vector < int > , greater < int > > pq ; for ( int i = 0 ; i < N ; i ++ ) { pq . push ( arr [ i ] ) ; } int prev = pq . top ( ) ; pq . pop ( ) ; int c = 1 ; int max = 1 ; while ( ! pq . empty ( ) ) { if ( pq . top ( ) - prev > 1 ) { c = 1 ; prev = pq . top ( ) ; pq . pop ( ) ; } else if ( pq . top ( ) - prev == 0 ) { prev = pq . top ( ) ; pq . pop ( ) ; } else { c ++ ; prev = pq . top ( ) ; pq . pop ( ) ; } if ( max < c ) { max = c ; } } return max ; } int main ( ) { int arr [ ] = { 1 , 9 , 3 , 10 , 4 , 20 , 2 } ; int n = 7 ; cout << " Length ▁ of ▁ the ▁ Longest ▁ consecutive ▁ subsequence ▁ " " is ▁ " << findLongestConseqSubseq ( arr , n ) ; return 0 ; }