Find length of the longest sub-sequence in C++

In this post first we are going to understand the problem to find the length of longest sub-sequence of an array and then we will write a C++ program to implement the same. Let’s understand the problem first:

Given: An array arr[ ] of N integers.

Problem: To find the length of the longest subsequence such that adjacent elements of the subsequence have at least one digit in common.

Example:

Input: arr[] = {1, 12, 44, 29, 33, 96, 89}
Output: 5
The longest sub-sequence is {1 12 29 96 89}

Input: arr[] = {12, 23, 45, 43, 36, 97}
Output: 4
The longest sub-sequence is {12 23 43 36}

Solution: Store the length of longest subsequence for each digit present in an element of the array.

• dp[i][d] represents the length of the longest sub-sequence up to ith element if digit d is the common digit.
• Declare a cnt array and set cnt[d] = 1 for each digit present in current element.
• Consider each digit d as common digit and find maximum length sub-sequence ending at arr[i] as dp[i][d] = max(dp[j][d]+1) (0<=j<i).
• Also find a local maximum max(dp[i][d]) for current element.
• After finding local maximum update dp[i][d] for all digits present in the current element to a local maximum.
• This is required as local maximum represents maximum length of subsequence for an element having digit d.

E.g. Consider arr[] = {24, 49, 96}.
The local maximum for 49 is 2 obtain from digit 4.
This local maximum will be used in finding the local maximum for 96 with common digit 9.
For that it is required for all digits in 49, dp[i][d] should be set to local maximum.

C++ program to find the length of the longest sub-sequence such that adjacent elements of the subsequence have at least one digit in common:

You can also execute this code on our online compiler.

// C++ program to find maximum length subsequence 
// such that adjacent elements have at least 
// one common digit 
#include <bits/stdc++.h> 
using namespace std; 

// Returns length of maximum length subsequence 
int findSubsequence(int arr[], int n) 
{ 

    // To store the length of the 
    // maximum length subsequence 
    int len = 1; 

    // To store current element arr[i] 
    int tmp; 

    int i, j, d; 

    // To store the length of the sub-sequence 
    // ending at index i and having common digit d 
    int dp[n][10]; 

    memset(dp, 0, sizeof(dp)); 

    // To store digits present in current element 
    int cnt[10]; 

    // To store length of maximum length subsequence 
    // ending at index i 
    int locMax; 

    // For first element maximum length is 1 for 
    // each digit 
    tmp = arr[0]; 
    while (tmp > 0) { 
        dp[0][tmp % 10] = 1; 
        tmp /= 10; 
    } 

    // Find digits of each element, then find length 
    // of subsequence for each digit and then find 
    // local maximum 
    for (i = 1; i < n; i++) { 
        tmp = arr[i]; 
        locMax = 1; 
        memset(cnt, 0, sizeof(cnt)); 

        // Find digits in current element 
        while (tmp > 0) { 
            cnt[tmp % 10] = 1; 
            tmp /= 10; 
        } 

        // For each digit present find length of 
        // subsequence and find local maximum 
        for (d = 0; d <= 9; d++) { 
            if (cnt[d]) { 
                dp[i][d] = 1; 
                for (j = 0; j < i; j++) { 
                    dp[i][d] = max(dp[i][d], dp[j][d] + 1); 
                    locMax = max(dp[i][d], locMax); 
                } 
            } 
        } 

        // Update value of dp[i][d] for each digit 
        // present in current element to local maximum 
        // found. 
        for (d = 0; d <= 9; d++) { 
            if (cnt[d]) { 
                dp[i][d] = locMax; 
            } 
        } 

        // Update maximum length with local maximum 
        len = max(len, locMax); 
    } 

    return len; 
} 

// Driver code 
int main() 
{ 
    int arr[] = { 1, 12, 44, 29, 33, 96, 89 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 

    cout << findSubsequence(arr, n); 

    return 0; 
} 

OUTPUT:

5

Time Complexity: O(n²)

Comment below in case you find any issue with the problem or you want to provide any suggestion for me such that we improve the code together. If you need to more problems like this just discuss in comments.