Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la longitud de la subsecuencia creciente más larga posible seleccionando elementos de índices que son divisibles por todos los índices seleccionados previamente.
Nota: considere la indexación basada en 1
Ejemplos:
Entrada: arr[] = {1, 4, 2, 3, 6, 4, 9}
Salida: 3
Explicación: La forma óptima es seleccionar los elementos presentes en los índices 1, 3 y 6. La secuencia {1, 2, 4 } generado al seleccionar elementos de estos índices es creciente y cada índice es divisible por los índices seleccionados previamente.
Por lo tanto, la longitud es 3.Entrada: arr[] = {2, 3, 4, 5, 6, 7, 8, 9}
Salida: 4
Explicación: La forma óptima es seleccionar los elementos presentes en los índices 1, 2, 4 y 8. La secuencia {2 , 3, 5, 9} generado al seleccionar elementos de estos índices es creciente y cada índice es divisible por los índices seleccionados previamente.
Por lo tanto, la longitud es 4.
Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias de elementos de array posibles seleccionando de la secuencia de índices que son divisibles por todos los índices anteriores en la secuencia. Encuentre la longitud de todas estas subsecuencias e imprima la longitud máxima obtenida.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque Eficiente: Para optimizar el enfoque anterior, la idea es utilizar Programación Dinámica . Siga los pasos a continuación para resolver el problema:
- Inicialice una array dp[] de tamaño N . El i -ésimo índice en la tabla dp[] , es decir, dp[i] , representa la longitud de la subsecuencia más larga posible del tipo requerido obtenido hasta el i -ésimo índice.
- Recorra la array dp[] usando la variable i , y recorra todos los múltiplos de i con la variable j , de modo que 2*i ≤ j ≤ N .
- Para cada j , si arr[j] > arr[i] , actualice el valor dp[j] = max(dp[j], dp[i] + 1) para incluir la longitud de la subsecuencia más larga.
- De lo contrario, busque el siguiente índice.
- Después de completar los pasos anteriores, imprima el elemento máximo de la array dp[] como la longitud de la subsecuencia más larga.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find length of longest
// subsequence generated that
// satisfies the specified conditions
int findMaxLength(int N, vector<int> arr)
{
// Stores the length of longest
// subsequences of all lengths
vector<int> dp(N + 1, 1);
// Iterate through the given array
for (int i = 1; i <= N; i++) {
// Iterate through the multiples i
for (int j = 2 * i; j <= N; j += i) {
if (arr[i - 1] < arr[j - 1]) {
// Update dp[j] as maximum
// of dp[j] and dp[i] + 1
dp[j] = max(dp[j], dp[i] + 1);
}
}
}
// Return the maximum element in dp[]
// as the length of longest subsequence
return *max_element(dp.begin(), dp.end());
}
// Driver Code
int main()
{
vector<int> arr{ 2, 3, 4, 5, 6, 7, 8, 9 };
int N = arr.size();
// Function Call
cout << findMaxLength(N, arr);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find length of longest
// subsequence generated that
// satisfies the specified conditions
static int findMaxLength(int N, int[] arr)
{
// Stores the length of longest
// subsequences of all lengths
int[] dp = new int[N + 1];
Arrays.fill(dp, 1);
// Iterate through the given array
for(int i = 1; i <= N; i++)
{
// Iterate through the multiples i
for(int j = 2 * i; j <= N; j += i)
{
if (arr[i - 1] < arr[j - 1])
{
// Update dp[j] as maximum
// of dp[j] and dp[i] + 1
dp[j] = Math.max(dp[j], dp[i] + 1);
}
}
}
// Return the maximum element in dp[]
// as the length of longest subsequence
return Arrays.stream(dp).max().getAsInt();
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 3, 4, 5, 6, 7, 8, 9 };
int N = arr.length;
// Function Call
System.out.print(findMaxLength(N, arr));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to find length of longest # subsequence generated that # satisfies the specified conditions def findMaxLength(N, arr): # Stores the length of longest # subsequences of all lengths dp = [1] * (N + 1) # Iterate through the given array for i in range(1, N + 1): # Iterate through the multiples i for j in range(2 * i, N + 1, i): if (arr[i - 1] < arr[j - 1]): # Update dp[j] as maximum # of dp[j] and dp[i] + 1 dp[j] = max(dp[j], dp[i] + 1) # Return the maximum element in dp[] # as the length of longest subsequence return max(dp) # Driver Code if __name__ == '__main__': arr=[2, 3, 4, 5, 6, 7, 8, 9] N = len(arr) # Function Call print(findMaxLength(N, arr)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Linq;
class GFG{
// Function to find length of longest
// subsequence generated that
// satisfies the specified conditions
static int findMaxLength(int N, int[] arr)
{
// Stores the length of longest
// subsequences of all lengths
int[] dp = new int[N + 1];
for(int i = 1; i <= N; i++)
{
dp[i] = 1;
}
// Iterate through the given array
for(int i = 1; i <= N; i++)
{
// Iterate through the multiples i
for(int j = 2 * i; j <= N; j += i)
{
if (arr[i - 1] < arr[j - 1])
{
// Update dp[j] as maximum
// of dp[j] and dp[i] + 1
dp[j] = Math.Max(dp[j], dp[i] + 1);
}
}
}
// Return the maximum element in dp[]
// as the length of longest subsequence
return dp.Max();;
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 3, 4, 5, 6, 7, 8, 9 };
int N = arr.Length;
// Function Call
Console.WriteLine(findMaxLength(N, arr));
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// javascript program for the above approach
// Function to find length of longest
// subsequence generated that
// satisfies the specified conditions
function findMaxLength(N, arr) {
// Stores the length of longest
// subsequences of all lengths
var dp = Array(N + 1).fill(1);
// Iterate through the given array
for (i = 1; i <= N; i++) {
// Iterate through the multiples i
for (j = 2 * i; j <= N; j += i) {
if (arr[i - 1] < arr[j - 1]) {
// Update dp[j] as maximum
// of dp[j] and dp[i] + 1
dp[j] = Math.max(dp[j], dp[i] + 1);
}
}
}
// Return the maximum element in dp
// as the length of longest subsequence
return Math.max.apply(Math,dp);
}
// Driver Code
var arr = [ 2, 3, 4, 5, 6, 7, 8, 9 ];
var N = arr.length;
// Function Call
document.write(findMaxLength(N, arr));
// This code contributed by Rajput-Ji
</script>
4
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por vashisthamadhur2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA