Length of the longest increasing subsequence such that no two adjacent elements are coprime | CPP program to find the length of the longest increasing sub sequence from the given array such that no two adjacent elements are co prime ; Function to find the length of the longest increasing sub sequence from the given array such that no two adjacent elements are co prime ; To store dp and d value ; To store required answer ; For all elements in the array ; Initially answer is one ; For all it 's divisors ; Update the dp value ; Update the divisor value ; Check for required answer ; Update divisor of a [ i ] ; Return required answer ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100005 NEW_LINE int LIS ( int a [ ] , int n ) { int dp [ N ] , d [ N ] ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { dp [ a [ i ] ] = 1 ; for ( int j = 2 ; j * j <= a [ i ] ; j ++ ) { if ( a [ i ] % j == 0 ) { dp [ a [ i ] ] = max ( dp [ a [ i ] ] , dp [ d [ j ] ] + 1 ) ; dp [ a [ i ] ] = max ( dp [ a [ i ] ] , dp [ d [ a [ i ] / j ] ] + 1 ) ; d [ j ] = a [ i ] ; d [ a [ i ] / j ] = a [ i ] ; } } ans = max ( ans , dp [ a [ i ] ] ) ; d [ a [ i ] ] = a [ i ] ; } return ans ; } int main ( ) { int a [ ] = { 1 , 2 , 3 , 4 , 5 , 6 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << LIS ( a , n ) ; return 0 ; }