Longest Consecutive Subsequence - C++ Solution

1. Introduction

This blog post explores a common problem in array processing: finding the longest subsequence formed by consecutive integers. This problem is an excellent exercise in understanding hash sets and array manipulation in C++.

Problem

Given an integer array, the task is to find the length of the longest subsequence consisting of consecutive integers. The subsequence should contain all distinct values, and the elements can appear in any order.

Examples:

- Input: [2, 0, 6, 1, 5, 3, 7]

Output: 4

- Input: [1, 4, 4, 0, 2, 3]

Output: 5

- Input: [2, 4, 6, 3, 7, 4, 8, 1]

Output: 4

2. Solution Steps

1. Create a hash set and insert all array elements into it.

2. Iterate through the array and for each element:

a. Check if it is the start of a subsequence (i.e., the previous element is not in the set).

b. If so, count the length of the consecutive subsequence starting from this element.

3. Keep track of the maximum length found during the iteration.

4. Return the maximum length.

3. Code Program

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

// Function to find the length of the longest consecutive subsequence
int longestConsecutiveSubsequence(vector<int>& nums) {
    unordered_set<int> elements(nums.begin(), nums.end());
    int maxLength = 0;

    for (int num : nums) {
        // Check if num is the start of a subsequence
        if (elements.find(num - 1) == elements.end()) {
            int currentNum = num;
            int currentLength = 1;

            // Count the length of the subsequence
            while (elements.find(currentNum + 1) != elements.end()) {
                currentNum += 1;
                currentLength += 1;
            }

            maxLength = max(maxLength, currentLength);
        }
    }

    return maxLength;
}

int main() {
    vector<int> nums = {2, 0, 6, 1, 5, 3, 7};
    cout << "Length of the longest consecutive subsequence: " << longestConsecutiveSubsequence(nums) << endl;
    return 0;
}

Output:

Length of the longest consecutive subsequence: 4

Explanation:

The longestConsecutiveSubsequence function first creates a hash set of all elements in the array. It then iterates through the array, and for each element, checks if it is the start of a new subsequence. If it is, the function counts the length of this subsequence by continuously checking for the next consecutive number in the set. The length of the longest subsequence found in this manner is returned. This approach efficiently identifies the longest subsequence of consecutive numbers in the array.