Given an array arr[] of size N. The task is to find the length of the longest subsequence from the given array such that the sequence is strictly increasing and no two adjacent elements are coprime.
Note: The elements in the given array are strictly increasing in order (1 <= a[i] <= 105)
Examples:
Input : a[] = { 1, 2, 3, 4, 5, 6}
Output : 3
Explanation : Possible sub sequences are {1}, {2}, {3}, {4}, {5}, {6}, {2, 4}, {2, 4, 6}, {2, 6}, {4, 6}, {3, 6}.
The subsequence {2, 4, 6} has the longest length.Input : a[] = { 1, 1, 1, 1}
Output : 1
Approach: The main idea is to use the concept of Dynamic programming. Let’s define dp[x] as the maximal value of the length of the subsequence whose last element is x, and define d[i] as the (maximal value of dp[x] where x is divisible by i).
We should calculate dp[x] in the increasing order of x. The value of dp[x] is (maximal value of d[i] where i is a divisor of x) + 1. After we calculate dp[x], for each divisor i of x, we should update d[i] too. This algorithm works in O(N*logN) because the sum of the number of the divisors from 1 to N is O(N*logN).
Note: There is a corner case. When the set is {1}, you should output 1.
Below is the implementation of the above approach:
C++
// 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#include <bits/stdc++.h>using namespace std;#define N 100005// Function to find the length of the// longest increasing sub sequence from the given array// such that no two adjacent elements are co primeint LIS(int a[], int n){ // To store dp and d value int dp[N], d[N]; // To store required answer int ans = 0; // For all elements in the array for (int i = 0; i < n; i++) { // Initially answer is one dp[a[i]] = 1; // For all it's divisors for (int j = 2; j * j <= a[i]; j++) { if (a[i] % j == 0) { // Update the dp value dp[a[i]] = max(dp[a[i]], dp[d[j]] + 1); dp[a[i]] = max(dp[a[i]], dp[d[a[i] / j]] + 1); // Update the divisor value d[j] = a[i]; d[a[i] / j] = a[i]; } } // Check for required answer ans = max(ans, dp[a[i]]); // Update divisor of a[i] d[a[i]] = a[i]; } // Return required answer return ans;}// Driver codeint main(){ int a[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof(a) / sizeof(a[0]); cout << LIS(a, n); return 0;} |
Java
// Java program to find the length // of the longest increasing sub// sequence from the given array // such that no two adjacent // elements are co prime class GFG{ static int N=100005; // Function to find the length of the // longest increasing sub sequence // from the given array such that // no two adjacent elements are co prime static int LIS(int a[], int n) { // To store dp and d value int dp[]=new int[N], d[]=new int[N]; // To store required answer int ans = 0; // For all elements in the array for (int i = 0; i < n; i++) { // Initially answer is one dp[a[i]] = 1; // For all it's divisors for (int j = 2; j * j <= a[i]; j++) { if (a[i] % j == 0) { // Update the dp value dp[a[i]] = Math.max(dp[a[i]], dp[d[j]] + 1); dp[a[i]] = Math.max(dp[a[i]], dp[d[a[i] / j]] + 1); // Update the divisor value d[j] = a[i]; d[a[i] / j] = a[i]; } } // Check for required answer ans = Math.max(ans, dp[a[i]]); // Update divisor of a[i] d[a[i]] = a[i]; } // Return required answer return ans; } // Driver code public static void main(String args[]) { int a[] = { 1, 2, 3, 4, 5, 6 }; int n = a.length; System.out.print( LIS(a, n)); }} // This code is contributed by Arnab Kundu |
Python3
# Python3 program to find the length of the# longest increasing sub sequence from the # given array such that no two adjacent # elements are co primeN = 100005# Function to find the length of the# longest increasing sub sequence from # the given array such that no two # adjacent elements are co primedef LIS(a, n): # To store dp and d value dp = [0 for i in range(N)] d = [0 for i in range(N)] # To store required answer ans = 0 # For all elements in the array for i in range(n): # Initially answer is one dp[a[i]] = 1 # For all it's divisors for j in range(2, a[i]): if j * j > a[i]: break if (a[i] % j == 0): # Update the dp value dp[a[i]] = max(dp[a[i]], dp[d[j]] + 1) dp[a[i]] = max(dp[a[i]], dp[d[a[i] // j]] + 1) # Update the divisor value d[j] = a[i] d[a[i] // j] = a[i] # Check for required answer ans = max(ans, dp[a[i]]) # Update divisor of a[i] d[a[i]] = a[i] # Return required answer return ans# Driver codea = [1, 2, 3, 4, 5, 6]n = len(a)print(LIS(a, n))# This code is contributed by mohit kumar |
C#
// C# program to find the length // of the longest increasing sub // sequence from the given array // such that no two adjacent // elements are co prime using System;class GFG { static int N = 100005; // Function to find the length of the // longest increasing sub sequence // from the given array such that // no two adjacent elements are co prime static int LIS(int []a, int n) { // To store dp and d value int []dp = new int[N]; int []d = new int[N]; // To store required answer int ans = 0; // For all elements in the array for (int i = 0; i < n; i++) { // Initially answer is one dp[a[i]] = 1; // For all it's divisors for (int j = 2; j * j <= a[i]; j++) { if (a[i] % j == 0) { // Update the dp value dp[a[i]] = Math.Max(dp[a[i]], dp[d[j]] + 1); dp[a[i]] = Math.Max(dp[a[i]], dp[d[a[i] / j]] + 1); // Update the divisor value d[j] = a[i]; d[a[i] / j] = a[i]; } } // Check for required answer ans = Math.Max(ans, dp[a[i]]); // Update divisor of a[i] d[a[i]] = a[i]; } // Return required answer return ans; } // Driver code public static void Main() { int []a = { 1, 2, 3, 4, 5, 6 }; int n = a.Length; Console.WriteLine(LIS(a, n)); }} // This code is contributed by Ryuga |
PHP
<?php// PHP program to find the length of the// longest increasing sub sequence from // the given array such that no two adjacent// elements are co prime$N = 100005;// Function to find the length of the// longest increasing sub sequence from // the given array such that no two // adjacent elements are co primefunction LIS($a, $n){ // To store dp and d value $dp = array(); $d = array(); // To store required answer $ans = 0; // For all elements in the array for ($i = 0; $i < $n; $i++) { // Initially answer is one $dp[$a[$i]] = 1; // For all it's divisors for ($j = 2; $j * $j <= $a[$i]; $j++) { if ($a[$i] % $j == 0) { // Update the dp value $dp[$a[$i]] = max($dp[$a[$i]], $dp[$d[$j]] + 1); $dp[$a[$i]] = max($dp[$a[$i]], $dp[$d[$a[$i] / $j]] + 1); // Update the divisor value $d[$j] = $a[$i]; $d[$a[$i] / $j] = $a[$i]; } } // Check for required answer $ans = max($ans, $dp[$a[$i]]); // Update divisor of a[i] $d[$a[$i]] = $a[$i]; } // Return required answer return $ans;}// Driver code$a = array(1, 2, 3, 4, 5, 6);$n = sizeof($a);echo LIS($a, $n);// This code is contributed // by Akanksha Rai?> |
Javascript
<script>// Javascript program to find the length of the// longest increasing sub sequence from// the given array such that no two adjacent// elements are co primelet N = 100005;// Function to find the length of the// longest increasing sub sequence from// the given array such that no two// adjacent elements are co primefunction LIS(a, n){ // To store dp and d value let dp = new Array(); let d = new Array(); // To store required answer let ans = 0; // For all elements in the array for (let i = 0; i < n; i++) { // Initially answer is one dp[a[i]] = 1; // For all it's divisors for (j = 2; j * j <= a[i]; j++) { if (a[i] % j == 0) { // Update the dp value dp[a[i]] = Math.max(dp[a[i]], dp[d[j]] + 1); dp[a[i]] = Math.max(dp[a[i]], dp[d[a[i] / j]] + 1); // Update the divisor value d[j] = a[i]; d[a[i] / j] = a[i]; } } // Check for required answer ans = Math.max(ans, dp[a[i]]); // Update divisor of a[i] d[a[i]] = a[i]; } // Return required answer return ans;}// Driver codelet a = [1, 2, 3, 4, 5, 6];let n = a.length;document.write(LIS(a, n));// This code is contributed// by _saurabh_jaiswal</script> |
Output:
3
Time Complexity: O(N* log(N))
Auxiliary Space: O(N), since N extra space has been taken.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
