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: 3
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:
- Tomemos todos los números en orden creciente.
- 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) .
- 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 .
- 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