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, 60Input: 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] elementvoid printLDS(vector<int>& Max){ // Traverse the Max[] for (auto& it : Max) { cout << it << ' '; }}// Function to construct and print Longest// Dividing Subsequencevoid 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 Codeint main(){ int arr[] = { 2, 11, 16, 12, 36, 60, 71 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call LongestDividingSeq(arr, N); return 0;} |
Java
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
# Python3 program for the above approach# Function to print LDS[i] elementdef printLDS(Max): # Traverse the Max[] for it in Max: print(it, end = " ")# Function to construct and print # Longest Dividing Subsequencedef 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 Codearr = [ 2, 11, 16, 12, 36, 60, 71 ]N = len(arr)# Function callLongestDividingSeq(arr, N);# This code is contributed by ANKITKUMAR34 |
C#
// C# program to implement above approachusing 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. |
Javascript
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 callLongestDividingSeq(arr, N);// This code is contributed by Aditya Sharma |
Output
2 12 36 2 12 60
Time Complexity: O(N2)
Auxiliary Space: O(N2)
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!
