Longest subsequence such that adjacent elements have at least one common digit | C ++ program to find maximum length subsequence such that adjacent elements have at least one common digit ; Returns length of maximum length subsequence ; To store the length of the maximum length subsequence ; To store current element arr [ i ] ; To store the length of the sub - sequence ending at index i and having common digit d ; To store digits present in current element ; To store length of maximum length subsequence ending at index i ; For first element maximum length is 1 for each digit ; Find digits of each element , then find length of subsequence for each digit and then find local maximum ; Find digits in current element ; For each digit present find length of subsequence and find local maximum ; Update value of dp [ i ] [ d ] for each digit present in current element to local maximum found . ; Update maximum length with local maximum ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findSubsequence ( int arr [ ] , int n ) { int len = 1 ; int tmp ; int i , j , d ; int dp [ n ] [ 10 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; int cnt [ 10 ] ; int locMax ; tmp = arr [ 0 ] ; while ( tmp > 0 ) { dp [ 0 ] [ tmp % 10 ] = 1 ; tmp /= 10 ; } for ( i = 1 ; i < n ; i ++ ) { tmp = arr [ i ] ; locMax = 1 ; memset ( cnt , 0 , sizeof ( cnt ) ) ; while ( tmp > 0 ) { cnt [ tmp % 10 ] = 1 ; tmp /= 10 ; } 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 ) ; } } } for ( d = 0 ; d <= 9 ; d ++ ) { if ( cnt [ d ] ) { dp [ i ] [ d ] = locMax ; } } len = max ( len , locMax ) ; } return len ; } int main ( ) { int arr [ ] = { 1 , 12 , 44 , 29 , 33 , 96 , 89 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << findSubsequence ( arr , n ) ; return 0 ; }