Print all Longest dividing subsequence in an Array
Last Updated : 17 Feb, 2023
Given an array arr[] of N integers, the task is to print all the element of Longest Dividing Subsequence formed by the given array. If we have more than one sequence with maximum length then print all of them. Examples:
Input: arr[] = { 2, 11, 16, 12, 36, 60, 71 }
Output: 2 12 36 2 12 60
Explanation: There are two subsequence with maximum length 3. 1. 2, 12, 36 2. 2, 12, 60
Input: arr[] = { 2, 4, 16, 32, 64, 60, 12 };
Output: 2 4 16 32 64
Explanation: There is only one subsequence with maximum length 5. 1. 2 4 16 32 64
Approach:
- Declare a 2D array LDS[][] which stores the Longest Dividing Subsequence.
- Traverse the given array arr[] and find the longest dividing subsequence till current element by using the approach discussed in this article.
- Traverse the given LDS[][] array, and print all the elements of the sequence with maximum length.
Below is the implementation of the above approach:
C++ // C++ program for the above approach #include "bits/stdc++.h" using namespace std; // Function to print LDS[i] element void printLDS(vector<int>& Max) { // Traverse the Max[] for (auto& it : Max) { cout << it << ' '; } } // Function to construct and print Longest // Dividing Subsequence void LongestDividingSeq(int arr[], int N) { // 2D vector for storing sequences vector<vector<int> > LDS(N); // Push the first element to LDS[][] LDS[0].push_back(arr[0]); // Iterate over all element for (int i = 1; i < N; i++) { // Loop for every index till i for (int j = 0; j < i; j++) { // if current elements divides // arr[i] and length is greater // than the previous index, then // insert the current element // to the sequences LDS[i] if ((arr[i] % arr[j] == 0) && (LDS[i].size() < LDS[j].size() + 1)) LDS[i] = LDS[j]; } // L[i] ends with arr[i] LDS[i].push_back(arr[i]); } int maxLength = 0; // LDS stores the sequences till // each element of arr[] // Traverse the LDS[][] to find the // the maximum length for (int i = 0; i < N; i++) { int x = LDS[i].size(); maxLength = max(maxLength, x); } // Print all LDS with maximum length for (int i = 0; i < N; i++) { // Find size int size = LDS[i].size(); // If size = maxLength if (size == maxLength) { // Print LDS printLDS(LDS[i]); cout << '\n'; } } } // Driver Code int main() { int arr[] = { 2, 11, 16, 12, 36, 60, 71 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call LongestDividingSeq(arr, N); return 0; } import java.util.*; public class Main { static void printLDS(ArrayList<Integer> Max) { // Traverse the Max[] for (int it : Max) { System.out.print(it + " "); } } static void LongestDividingSeq(int[] arr, int N) { // 2D list for storing sequences ArrayList<ArrayList<Integer> > LDS = new ArrayList<ArrayList<Integer> >(); for (int i = 0; i <= N; i++) { LDS.add(new ArrayList<Integer>()); } LDS.get(0).add(arr[0]); // Iterate over all element for (int i = 1; i < N; i++) { // Loop for every index till i for (int j = 0; j < i; j++) { // if current elements divides arr[i] and // length is greater than the previous // index, then insert the current element to // the sequences LDS[i] if ((arr[i] % arr[j] == 0) && (LDS.get(i).size() < LDS.get(j).size() + 1)) LDS.set(i, new ArrayList<Integer>( LDS.get(j))); } // L[i] ends with arr[i] LDS.get(i).add(arr[i]); } int maxLength = 0; // LDS stores the sequences till each element of // arr[] Traverse the LDS[][] to find the the // maximum length for (int i = 0; i < N; i++) { int x = LDS.get(i).size(); maxLength = Math.max(maxLength, x); } // Print all LDS with maximum length for (int i = 0; i < N; i++) { // Find size int size = LDS.get(i).size(); // If size = maxLength if (size == maxLength) { // Print LDS printLDS(LDS.get(i)); System.out.println(); } } } public static void main(String[] args) { int[] arr = { 2, 11, 16, 12, 36, 60, 71 }; int N = arr.length; LongestDividingSeq(arr, N); } } # Python3 program for the above approach # Function to print LDS[i] element def printLDS(Max): # Traverse the Max[] for it in Max: print(it, end = " ") # Function to construct and print # Longest Dividing Subsequence def LongestDividingSeq(arr, N): # 2D vector for storing sequences LDS = [[] for i in range(N)] # Push the first element to LDS[][] LDS[0].append(arr[0]) # Iterate over all element for i in range(1, N): # Loop for every index till i for j in range(i): # If current elements divides # arr[i] and length is greater # than the previous index, then # insert the current element # to the sequences LDS[i] if ((arr[i] % arr[j] == 0) and (len(LDS[i]) < len(LDS[j]) + 1)): LDS[i] = LDS[j].copy() # L[i] ends with arr[i] LDS[i].append(arr[i]) maxLength = 0 # LDS stores the sequences till # each element of arr[] # Traverse the LDS[][] to find # the maximum length for i in range(N): x = len(LDS[i]) maxLength = max(maxLength, x) # Print all LDS with maximum length for i in range(N): # Find size size = len(LDS[i]) # If size = maxLength if (size == maxLength): # Print LDS printLDS(LDS[i]) print() # Driver Code arr = [ 2, 11, 16, 12, 36, 60, 71 ] N = len(arr) # Function call LongestDividingSeq(arr, N); # This code is contributed by ANKITKUMAR34
// C# program to implement above approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Function to print LDS[i] element static void printLDS(List<int> Max) { // Traverse the Max[] foreach (int it in Max) { Console.Write(it + " "); } } // Function to construct and print Longest // Dividing Subsequence static void LongestDividingSeq(int[] arr, int N) { // 2D vector for storing sequences List<List<int>> LDS = new List<List<int>>(); for(int i = 0 ; i < N ; i++){ LDS.Add(new List<int>()); } // Push the first element to LDS[][] LDS[0].Add(arr[0]); // Iterate over all element for (int i = 1 ; i < N ; i++) { // Loop for every index till i for (int j = 0 ; j < i ; j++) { // if current elements divides // arr[i] and length is greater // than the previous index, then // insert the current element // to the sequences LDS[i] if ((arr[i] % arr[j] == 0) && (LDS[i].Count < LDS[j].Count + 1)){ LDS[i] = new List<int>(LDS[j]); } } // L[i] ends with arr[i] LDS[i].Add(arr[i]); } int maxLength = 0; // LDS stores the sequences till // each element of arr[] // Traverse the LDS[][] to find the // the maximum length for (int i = 0 ; i < N ; i++) { int x = LDS[i].Count; maxLength = Math.Max(maxLength, x); } // Print all LDS with maximum length for (int i = 0 ; i < N ; i++) { // Find size int size = LDS[i].Count; // If size = maxLength if (size == maxLength) { // Print LDS printLDS(LDS[i]); Console.WriteLine(""); } } } // Driver code public static void Main(string[] args){ int[] arr = new int[]{ 2, 11, 16, 12, 36, 60, 71 }; int N = arr.Length; // Function Call LongestDividingSeq(arr, N); } } // This code is contributed by subhamgoyal2014. function printLDS(Max){ // Traverse the Max[] console.log(Max.join(" ")); } function LongestDividingSeq(arr, n){ // 2D vector for storing sequences let LDS = []; for(let i = 0; i <= n; i++){ LDS.push([]); } LDS[0].push(arr[0]); // Iterate over all element for(let i = 1; i < n; i++){ // Loop for every index till i for(let j = 0; j < i; j++){ // If current elements divides // arr[i] and lengths is greater // than the previous index, then // insert the current element // to the sequence LDS[i] if((arr[i]%arr[j] == 0) && (LDS[i].length < (LDS[j].length+1))){ LDS[i] = LDS[j].slice(); } } // L[i] ends with arr[i] LDS[i].push(arr[i]); } let maxlength = 0; // LDS stores the sequences till // each element of arr[] // TRaverse the LDS[][] to find the // the maximum length for(let i = 0; i < n; i++){ let x = LDS[i].length; maxlength = Math.max(maxlength, x); } // Print all the LDS with maximum length for(let i = 0; i < n; i++){ // find size let size = LDS[i].length; // if size == maxlength if(size == maxlength){ // Print LDS // printLDS(LDS[i]); console.log(LDS[i].join(" ")); // console.log(); } } } // Driver code let arr = [2, 11, 16, 12, 36, 60, 71]; let N = arr.length; // Function call LongestDividingSeq(arr, N); // This code is contributed by Aditya Sharma Time Complexity: O(N2)
Auxiliary Space: O(N2)
Similar Reads
Longest subsequence of even numbers in an Array Given an array arr[] containing N integers, the task is to print the length of the longest subsequence of even numbers in the array. Examples: Input: arr[] = {3, 4, 11, 2, 9, 21} Output: 2 Explanation: The longest subsequence containing even numbers is {4, 2}. Hence, the answer is 2. Input: arr[] =
5 min read
Printing Longest Increasing Subsequence (LIS) Given a sequence of numbers, the task is to find and print the Longest Increasing Subsequence (LIS), the longest subsequence where each element is strictly greater than the previous one. If multiple LIS of the same maximum length exist, we must select the one that appears first based on the lexicogr
15+ min read
Longest dividing subsequence You are given an array A of size N. Your task is to find the length of largest dividing sub sequence.A dividing sequence is a sequence a1, a2, …, aN where ai divides aj whenever i < j. For example, 3, 15, 60, 720 is a dividing sequence. input- The first line of each test case is N, where N is the
5 min read
Longest alternative parity subsequence We are given an array a of size N. The task is to print the length of the longest alternative odd/even or even/odd subsequence. Examples: Input: a[] = { 13, 16, 8, 9, 32, 10 } Output: 4 {13, 16, 9, 10} or any other subsequence of length 4 can be the answer. Input: a[] = {1, 2, 3, 3, 9} Output: 3 App
7 min read
Length of longest increasing prime subsequence from a given array Given an array arr[] consisting of N positive integers, the task is to find the length of the longest increasing subsequence consisting of Prime Numbers in the given array. Examples: Input: arr[] = {1, 2, 5, 3, 2, 5, 1, 7}Output: 4Explanation:The Longest Increasing Prime Subsequence is {2, 3, 5, 7}.
9 min read
Longest subsequence forming an Arithmetic Progression (AP) Given an array arr[] consisting of N integers, the task is to find the length of the longest subsequence that forms an Arithmetic Progression. Examples: Input: arr[] = {5, 10, 15, 20, 25, 30}Output: 6Explanation:The whole set is in AP having common difference = 5.Therefore, the length is 4. Input: a
13 min read