Encuentre el subconjunto divisor más grande en la array

Dada una array arr[] de N enteros, la tarea es encontrar el subconjunto más grande de arr[] tal que en cada par de números de ese subconjunto, un número sea divisor del otro.
Ejemplos: 

Entrada: arr[] = {1, 2, 3, 4, 5} 
Salida: 4 2 1 
Todos los pares posibles de la subsecuencia son: 
(4, 2) -> 4 % 2 = 0 
(4, 1) -> 4 % 1 = 0 
y (2, 1) -> 2 % 1 = 0
Entrada: arr[] = {1, 3, 4, 9} 
Salida: 1 3 9  

Enfoque: Aquí la tarea es encontrar el subconjunto más grande donde en cada par de números, uno es divisible por el otro, es decir, para la secuencia a ₁ , a ₂ , a ₃ … a _k donde a ₁ ≤ a ₂ ≤ … ≤ a _k y a _i+1 % a _i = 0 para cada i . Esta secuencia se puede encontrar usando programación dinámica (similar a la subsecuencia creciente más larga ).
A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the required subsequence
void findSubSeq(int arr[], int n)
{
 
    // Sort the array
    sort(arr, arr + n);
 
    // Keep a count of the length of the
    // subsequence and the previous element
    int count[n] = { 1 };
    int prev[n] = { -1 };
 
    // Set the initial values
    memset(count, 1, sizeof(count));
    memset(prev, -1, sizeof(prev));
 
    // Maximum length of the subsequence and
    // the last element
    int max = 0;
    int maxprev = -1;
 
    // Run a loop for every element
    for (int i = 0; i < n; i++) {
 
        // Check for all the divisors
        for (int j = i - 1; j >= 0; j--) {
 
            // If the element is a divisor and the length
            // of subsequence will increase by adding
            // j as previous element of i
            if (arr[i] % arr[j] == 0
                && count[j] + 1 > count[i]) {
 
                // Increase the count
                count[i] = count[j] + 1;
                prev[i] = j;
            }
        }
 
        // Update the max count
        if (max < count[i]) {
            max = count[i];
            maxprev = i;
        }
    }
 
    // Get the last index of the subsequence
    int i = maxprev;
    while (i >= 0) {
 
        // Print the element
        if (arr[i] != -1)
            cout << arr[i] << " ";
 
        // Move the index to the previous element
        i = prev[i];
    }
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(int);
 
    findSubSeq(arr, n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
class GFG
{
     
    // Function to find the required subsequence
    static void findSubSeq(int arr[], int n)
    {
     
        // Sort the array
        Arrays.sort(arr);
     
        // Keep a count of the length of the
        // subsequence and the previous element
        int count[] = new int[n];
        int prev[] = new int[n];
     
        int i, j;
         
        // Set the initial values
        for(i = 0 ; i < n; i++)
        count[i] = 1;
         
        for(j = 0; j < n; j++)
            prev[j] = -1;
     
        // Maximum length of the subsequence and
        // the last element
        int max = 0;
        int maxprev = -1;
     
        // Run a loop for every element
        for ( i = 0; i < n; i++)
        {
     
            // Check for all the divisors
            for ( j = i - 1; j >= 0; j--)
            {
     
                // If the element is a divisor and
                // the length of subsequence will
                // increase by adding j as
                // previous element of i
                if (arr[i] % arr[j] == 0 &&
                    count[j] + 1 > count[i])
                {
     
                    // Increase the count
                    count[i] = count[j] + 1;
                    prev[i] = j;
                }
            }
     
            // Update the max count
            if (max < count[i])
            {
                max = count[i];
                maxprev = i;
            }
        }
     
        // Get the last index of the subsequence
        i = maxprev;
        while (i >= 0)
        {
     
            // Print the element
            if (arr[i] != -1)
                System.out.print(arr[i] + " ");
     
            // Move the index to the previous element
            i = prev[i];
        }
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr[] = { 1, 2, 3, 4, 5 };
        int n = arr.length;
     
        findSubSeq(arr, n);
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to find the required subsequence
def findSubSeq(arr, n) :
 
    # Sort the array
    arr.sort();
 
    # Keep a count of the length of the
    # subsequence and the previous element
    # Set the initial values
    count = [1] * n;
    prev = [-1] * n;
 
    # Maximum length of the subsequence and
    # the last element
    max = 0;
    maxprev = -1;
 
    # Run a loop for every element
    for i in range(n) :
 
        # Check for all the divisors
        for j in range(i - 1, -1, -1) :
 
            # If the element is a divisor and the length
            # of subsequence will increase by adding
            # j as previous element of i
            if (arr[i] % arr[j] == 0 and
                count[j] + 1 > count[i]) :
 
                # Increase the count
                count[i] = count[j] + 1;
                prev[i] = j;
 
        # Update the max count
        if (max < count[i]) :
            max = count[i];
            maxprev = i;
             
    # Get the last index of the subsequence
    i = maxprev;
    while (i >= 0) :
 
        # Print the element
        if (arr[i] != -1) :
            print(arr[i], end = " ");
 
        # Move the index to the previous element
        i = prev[i];
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 1, 2, 3, 4, 5 ];
    n = len(arr);
 
    findSubSeq(arr, n);
     
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
using System.Collections;
 
class GFG
{
     
    // Function to find the required subsequence
    static void findSubSeq(int []arr, int n)
    {
     
        // Sort the array
        Array.Sort(arr);
     
        // Keep a count of the length of the
        // subsequence and the previous element
        int []count = new int[n];
        int []prev = new int[n];
     
        int i, j;
         
        // Set the initial values
        for(i = 0; i < n; i++)
        count[i] = 1;
         
        for(j = 0; j < n; j++)
            prev[j] = -1;
     
        // Maximum length of the subsequence 
        // and the last element
        int max = 0;
        int maxprev = -1;
     
        // Run a loop for every element
        for ( i = 0; i < n; i++)
        {
     
            // Check for all the divisors
            for ( j = i - 1; j >= 0; j--)
            {
     
                // If the element is a divisor and
                // the length of subsequence will
                // increase by adding j as
                // previous element of i
                if (arr[i] % arr[j] == 0 &&
                    count[j] + 1 > count[i])
                {
     
                    // Increase the count
                    count[i] = count[j] + 1;
                    prev[i] = j;
                }
            }
     
            // Update the max count
            if (max < count[i])
            {
                max = count[i];
                maxprev = i;
            }
        }
     
        // Get the last index of the subsequence
        i = maxprev;
        while (i >= 0)
        {
     
            // Print the element
            if (arr[i] != -1)
                Console.Write(arr[i] + " ");
     
            // Move the index to the previous element
            i = prev[i];
        }
    }
     
    // Driver code
    public static void Main ()
    {
        int []arr = { 1, 2, 3, 4, 5 };
        int n = arr.Length;
     
        findSubSeq(arr, n);
    }
}
 
// This code is contributed by AnkitRai01

<script>
// Javascript implementation of above approach
 
// Function to find the required subsequence
function findSubSeq(arr, n)
{
    
    // Sort the array
    arr.sort();
 
    // Keep a count of the length of the
    // subsequence and the previous element
    var count = new Array(n);
    var prev = new Array(n);
 
    // Set the initial values
    count.fill(1);
    prev.fill(-1);
 
    // Maximum length of the subsequence and
    // the last element
    var max = 0;
    var maxprev = -1;
 
    // Run a loop for every element
    for (var i = 0; i < n; i++) {
 
        // Check for all the divisors
        for (var j = i - 1; j >= 0; j--) {
 
            // If the element is a divisor and the length
            // of subsequence will increase by adding
            // j as previous element of i
            if (arr[i] % arr[j] == 0
                && count[j] + 1 > count[i]) {
 
                // Increase the count
                count[i] = count[j] + 1;
                prev[i] = j;
            }
        }
 
        // Update the max count
        if (max < count[i]) {
            max = count[i];
            maxprev = i;
        }
    }
 
    // Get the last index of the subsequence
    var i = maxprev;
    while (i >= 0) {
 
        // Print the element
        if (arr[i] != -1)
            document.write( arr[i] + " ");
 
        // Move the index to the previous element
        i = prev[i];
    }
}
 
 
var arr = [ 1, 2, 3, 4, 5 ];
var n = arr.length;
findSubSeq(arr, n);
 
//This code is contributed by SoumikMondal
</script>

4 2 1

Complejidad temporal: O(N ² )

Espacio Auxiliar: O(1)