Longest consecutive subsequence.cpp

/*
Question Link-- 
https://practice.geeksforgeeks.org/problems/longest-consecutive-subsequence2449/1

Solved by https://www.linkedin.com/in/whynesspower

comments have been added for explanation 

*/

#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends
class Solution
{
public:
    // arr[] : the input array
    // N : size of the array arr[]

    //Function to return length of longest subsequence of consecutive integers.
    int findLongestConseqSubseq(int arr[], int n)
    {
        //using a Set to store elements.
        unordered_set<int> S;
        int ans = 0;

        //inserting all the array elements in Set.
        for (int i = 0; i < n; i++)
            S.insert(arr[i]);

        //checking each possible sequence from the start.
        for (int i = 0; i < n; i++)
        {
            //if current element is starting element of a sequence then only
            //we try to find out the length of sequence.
            if (S.find(arr[i] - 1) == S.end())
            {

                int j = arr[i];
                //then we keep checking whether the next consecutive elements
                //are present in Set and we keep incrementing the counter.
                while (S.find(j) != S.end())
                    j++;

                //storing the maximum count.
                ans = max(ans, j - arr[i]);
            }
        }
        //returning the length of longest subsequence
        return ans;
    }
};

// { Driver Code Starts.

// Driver program
int main()
{
    int t, n, i, a[100001];
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (i = 0; i < n; i++)
            cin >> a[i];
        Solution obj;
        cout << obj.findLongestConseqSubseq(a, n) << endl;
    }

    return 0;
} // } Driver Code Ends