Longest consecutive subsequence - Codeprg

Breaking

programing News Travel Computer Engineering Science Blogging Earning

Friday, 19 June 2020

Longest consecutive subsequence

Given an array of positive integers. Find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.

Shoes, Feet, Selfie, Passion, People

// { Driver Code Starts
#include <bits/stdc++.h>

using namespace std;

int findLongestConseqSubseq(int arr[], int n);

// 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];
        cout << findLongestConseqSubseq(a, n) << endl;
    }

    return 0;
} // } Driver Code Ends


// arr[] : the input array
// N : size of the array arr[]

// return the length of the longest subsequene of consecutive integers
int findLongestConseqSubseq(int arr[], int N) {
    //Your code here
    sort(arr, arr + N);
    int mx = 0, cnt = 0;
    for (int i = 0; i < N - 1; ++i) {
        if (arr[i] == arr[i + 1]) {
            continue;
        } else if (arr[i] == (arr[i + 1] - 1)) {
            cnt++;
        } else {
            if (mx < cnt)
                mx = cnt;
            cnt = 0;
        }

    }
    if (mx < cnt)
        mx = cnt;

    return mx + 1;

}