Tamaño del subconjunto divisible más grande en una array

Dada una array arr[] de tamaño N . La tarea es encontrar el tamaño del conjunto de números de la array dada de modo que cada número divida a otro o sea divisible por otro.

Ejemplos: 

Entrada: arr[] = {3, 4, 6, 8, 10, 18, 21, 24} 
Salida:
Uno de los conjuntos posibles con un tamaño máximo es {3, 6, 18} 

Entrada: arr[] = {2, 3, 4, 8, 16} 
Salida: 4

Acercarse:

  1. Tomemos todos los números en orden creciente.
  2. Tenga en cuenta que el conjunto X = x i , …, ?x k } es aceptable si y solo si x i divide x i+1 para (1 ≤ i ≤ k – 1) .
  3. Por lo tanto, dp[x] es igual a la longitud de la subsecuencia creciente adecuada más larga que comienza en el número x .
  4. Relación DP: dp[x] = max(dp[x], 1 + dp[y]) si x divide y .

A continuación se muestra la implementación del enfoque anterior: 

CPP

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
#define N 1000005
 
// Function to find the size of the
//largest divisible subarray
int maximum_set(int a[], int n)
{
    int dp[N] = { 0 };
 
    // Mark all elements of the array
    for (int i = 0; i < n; i++)
        dp[a[i]] = 1;
 
    int ans = 1;
 
    // Traverse reverse
    for (int i = N - 1; i >= 1; i--) {
 
        if (dp[i] != 0) {
            // For all multiples of i
            for (int j = 2 * i; j < N; j += i) {
                dp[i] = max(dp[i], 1 + dp[j]);
                ans = max(ans, dp[i]);
            }
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 4, 6, 8, 10, 18, 21, 24 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << maximum_set(arr, n);
 
    return 0;
}

Java

// Java implementation of the above approach
class GFG
{
     
    final static int N = 1000005 ;
     
    // Function to find the size of the
    //largest divisible subarray
    static int maximum_set(int a[], int n)
    {
        int dp[] = new int[N] ;
     
        // Mark all elements of the array
        for (int i = 0; i < n; i++)
            dp[a[i]] = 1;
     
        int ans = 1;
     
        // Traverse reverse
        for (int i = N - 1; i >= 1; i--)
        {
     
            if (dp[i] != 0)
            {
                // For all multiples of i
                for (int j = 2 * i; j < N; j += i)
                {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                    ans = Math.max(ans, dp[i]);
                }
            }
        }
     
        // Return the required answer
        return ans;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr[] = { 3, 4, 6, 8, 10, 18, 21, 24 };
     
        int n = arr.length;
     
        // Function call
        System.out.println(maximum_set(arr, n));
    }
}
 
// This code is contributed by AnkitRai01

Python

# Python3 implementation of the above approach
 
N = 1000005
 
# Function to find the size of the
# largest divisible subarray
def maximum_set(a, n):
    dp = [0 for i in range(N)]
 
    # Mark all elements of the array
    for i in a:
        dp[i] = 1
 
    ans = 1
 
    # Traverse reverse
    for i in range(N - 1, 0, -1):
 
        if (dp[i] != 0):
             
            # For all multiples of i
            for j in range(2 * i, N, i):
                dp[i] = max(dp[i], 1 + dp[j])
                ans = max(ans, dp[i])
 
    # Return the required answer
    return ans
 
# Driver code
 
arr = [3, 4, 6, 8, 10, 18, 21, 24]
 
n = len(arr)
 
# Function call
print(maximum_set(arr, n))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the above approach
using System;
 
class GFG
{
    static int N = 1000005 ;
     
    // Function to find the size of the
    //largest divisible subarray
    static int maximum_set(int []a, int n)
    {
        int []dp = new int[N] ;
     
        // Mark all elements of the array
        for (int i = 0; i < n; i++)
            dp[a[i]] = 1;
     
        int ans = 1;
     
        // Traverse reverse
        for (int i = N - 1; i >= 1; i--)
        {
     
            if (dp[i] != 0)
            {
                // For all multiples of i
                for (int j = 2 * i; j < N; j += i)
                {
                    dp[i] = Math.Max(dp[i], 1 + dp[j]);
                    ans = Math.Max(ans, dp[i]);
                }
            }
        }
     
        // Return the required answer
        return ans;
    }
     
    // Driver code
    public static void Main()
    {
        int []arr = { 3, 4, 6, 8, 10, 18, 21, 24 };
        int n = arr.Length;
     
        // Function call
        Console.WriteLine(maximum_set(arr, n));
    }
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
// Javascript implementation of the above approach
 
let N = 1000005
 
// Function to find the size of the
//largest divisible subarray
function maximum_set(a, n) {
    let dp = new Array(N).fill(0);
 
    // Mark all elements of the array
    for (let i = 0; i < n; i++)
        dp[a[i]] = 1;
 
    let ans = 1;
 
    // Traverse reverse
    for (let i = N - 1; i >= 1; i--) {
 
        if (dp[i] != 0) {
            // For all multiples of i
            for (let j = 2 * i; j < N; j += i) {
                dp[i] = Math.max(dp[i], 1 + dp[j]);
                ans = Math.max(ans, dp[i]);
            }
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
 
let arr = [3, 4, 6, 8, 10, 18, 21, 24];
 
let n = arr.length;
 
// Function call
document.write(maximum_set(arr, n));
 
 
</script>
Producción: 

3

 

Complejidad de tiempo: O(n*sqrt(n))
 

Publicación traducida automáticamente

Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *