Subsecuencia más grande tal que todos los índices y todos los valores son múltiplos individualmente

Dada una array arr[] de N enteros positivos, la tarea es encontrar la subsecuencia estrictamente creciente más grande de arr[] tal que los índices de los elementos seleccionados en arr[] y los elementos seleccionados sean múltiplos entre sí individualmente. 
Nota: considere la indexación basada en 1 para la array arr[] .
Ejemplos: 
 

Entrada: arr[] = {1, 4, 2, 3, 6, 4, 9} 
Salida: 3 
Explicación: 
Podemos elegir el índice 1, 3, 6 y los valores son 1, 2, 4: 
Aquí todo índice mayor es divisible por índice más pequeño y cada valor de índice mayor es mayor que el valor de índice más pequeño. 
Entrada: arr[] = {5, 3, 4, 6} 
Salida: 2 
Explicación: 
Podemos elegir el índice 1 y 3 y los valores son 3 y 6: 
Aquí, cada índice mayor es divisible por un índice menor y cada valor de índice mayor es mayor que el valor del índice más pequeño. 
 

Enfoque ingenuo: 
el enfoque ingenuo es simplemente generar todas las subsecuencias posibles y para cada subsecuencia verificar dos condiciones: 

• primero verifique si los elementos están en orden estrictamente creciente y
• en segundo lugar, compruebe si el índice de los elementos seleccionados en arr[] es múltiplo entre sí.

De todas las subsecuencias posibles que satisfagan las dos condiciones dadas, seleccione la subsecuencia más grande. 
Complejidad de tiempo: O( N * 2 ^N ) 
Espacio auxiliar: O( N )
Enfoque eficiente: 
podemos optimizar el código utilizando la programación dinámica evitando el cálculo redundante del subproblema repetido almacenando en caché su resultado.

1. Cree una array dp[] de tamaño igual al tamaño de arr[] , donde dp[i] representa el tamaño de la subsecuencia más grande hasta el i-ésimo índice que satisface las condiciones dadas. 
    
2. Inicialice la array dp[] con 0. 
    
3. Ahora, itere la array arr[] desde el final.
4. Para cada índice, busque los índices j que dividen el índice actual y verifique si el valor en el índice actual es mayor que el elemento en el índice j .
5. Si es así, actualice dp[j] como: 
    

dp[j] = max(dp[actual] + 1, dp[j]) 
 

Finalmente, recorra la array dp[] e imprima el valor máximo.
A continuación se muestra la implementación del enfoque eficiente:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that print maximum length
// of array
void maxLength(int arr[], int n)
{
    // dp[] array to store the
    // maximum length
    vector<int> dp(n, 1);
 
    for (int i = n - 1; i > 1; i--) {
 
        // Find all divisors of i
        for (int j = 1;
             j <= sqrt(i); j++) {
 
            if (i % j == 0) {
                int s = i / j;
 
                if (s == j) {
 
                    // If the current value
                    // is greater than the
                    // divisor's value
                    if (arr[i] > arr[s]) {
 
                        dp[s] = max(dp[i] + 1,
                                    dp[s]);
                    }
                }
                else {
 
                    // If current value
                    // is greater
                    // than the divisor's value
                    // and s is not equal
                    // to current index
                    if (s != i
                        && arr[i] > arr[s])
                        dp[s] = max(dp[i] + 1,
                                    dp[s]);
 
                    // Condition if current
                    // value is greater
                    // than the divisor's value
                    if (arr[i] > arr[j]) {
                        dp[j] = max(dp[i] + 1,
                                    dp[j]);
                    }
                }
            }
        }
    }
 
    int max = 0;
 
    // Computing the greatest value
    for (int i = 1; i < n; i++) {
        if (dp[i] > max)
            max = dp[i];
    }
 
    // Printing maximum length of array
    cout << max << "\n";
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 0, 1, 4, 2, 3, 6, 4, 9 };
    int size = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    maxLength(arr, size);
    return 0;
}

// Java program for the above approach
import java.util.*;
import java.io.*;
 
class GFG{
     
// Function that print maximum length
// of array
static void maxLength(int arr[], int n)
{
     
    // dp[] array to store the
    // maximum length
    int dp[] = new int[n];
    for(int i = 1; i < n; i++)
    {
        dp[i] = 1;
    }
 
    for(int i = n - 1; i > 1; i--)
    {
         
        // Find all divisors of i
        for(int j = 1;
                j <= Math.sqrt(i); j++)
        {
            if (i % j == 0)
            {
                int s = i / j;
 
                if (s == j)
                {
                     
                    // If the current value
                    // is greater than the
                    // divisor's value
                    if (arr[i] > arr[s])
                    {
                        dp[s] = Math.max(dp[i] + 1,
                                         dp[s]);
                    }
                }
                else
                {
                     
                    // If current value is greater
                    // than the divisor's value
                    // and s is not equal
                    // to current index
                    if (s != i && arr[i] > arr[s])
                        dp[s] = Math.max(dp[i] + 1,
                                         dp[s]);
     
                    // Condition if current
                    // value is greater
                    // than the divisor's value
                    if (arr[i] > arr[j])
                    {
                        dp[j] = Math.max(dp[i] + 1,
                                         dp[j]);
                    }
                }
            }
        }
    }
    int max = 0;
 
    // Computing the greatest value
    for(int i = 1; i < n; i++)
    {
        if (dp[i] > max)
            max = dp[i];
    }
     
    // Printing maximum length of array
    System.out.println(max);
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array arr[]
    int arr[] = { 0, 1, 4, 2, 3, 6, 4, 9 };
    int size = arr.length;
 
    // Function call
    maxLength(arr, size);
}
}
 
// This code is contributed by sanjoy_62

# Python3 program for the above approach
from math import *
 
# Function that print maximum length
# of array
def maxLength (arr, n):
 
    # dp[] array to store the
    # maximum length
    dp = [1] * n
 
    for i in range(n - 1, 1, -1):
 
        # Find all divisors of i
        for j in range(1, int(sqrt(i)) + 1):
            if (i % j == 0):
                s = i // j
 
                if (s == j):
 
                    # If the current value
                    # is greater than the
                    # divisor's value
                    if (arr[i] > arr[s]):
                        dp[s] = max(dp[i] + 1, dp[s])
 
                else:
                    # If current value
                    # is greater
                    # than the divisor's value
                    # and s is not equal
                    # to current index
                    if (s != i and arr[i] > arr[s]):
                        dp[s] = max(dp[i] + 1, dp[s])
 
                    # Condition if current
                    # value is greater
                    # than the divisor's value
                    if (arr[i] > arr[j]):
                        dp[j] = max(dp[i] + 1, dp[j])
 
    Max = 0
 
    # Computing the greatest value
    for i in range(1, n):
        if (dp[i] > Max):
            Max = dp[i]
 
    # Printing maximum length of array
    print(Max)
 
# Driver Code
if __name__ == '__main__':
 
    # Given array arr[]
    arr = [ 0, 1, 4, 2, 3, 6, 4, 9]
    size = len(arr)
 
    # Function call
    maxLength(arr, size)
 
# This code is contributed by himanshu77

// C# program for the above approach
using System;
 
class GFG{
 
// Function that print maximum length
// of array
static void maxLength(int[] arr, int n)
{
     
    // dp[] array to store the
    // maximum length
    int[] dp = new int[n];
    for(int i = 1; i < n; i++)
    {
        dp[i] = 1;
    }
 
    for(int i = n - 1; i > 1; i--)
    {
         
        // Find all divisors of i
        for(int j = 1;
                j <= Math.Sqrt(i); j++)
        {
            if (i % j == 0)
            {
                int s = i / j;
                 
                if (s == j)
                {
                     
                    // If the current value
                    // is greater than the
                    // divisor's value
                    if (arr[i] > arr[s])
                    {
                        dp[s] = Math.Max(dp[i] + 1,
                                         dp[s]);
                    }
                }
                else
                {
                     
                    // If current value is greater
                    // than the divisor's value
                    // and s is not equal
                    // to current index
                    if (s != i && arr[i] > arr[s])
                        dp[s] = Math.Max(dp[i] + 1,
                                         dp[s]);
     
                    // Condition if current
                    // value is greater
                    // than the divisor's value
                    if (arr[i] > arr[j])
                    {
                        dp[j] = Math.Max(dp[i] + 1,
                                         dp[j]);
                    }
                }
            }
        }
    }
    int max = 0;
 
    // Computing the greatest value
    for(int i = 1; i < n; i++)
    {
        if (dp[i] > max)
            max = dp[i];
    }
 
    // Printing maximum length of array
    Console.WriteLine(max);
}
 
// Driver Code
public static void Main()
{
     
    // Given array arr[]
    int[] arr = new int[] { 0, 1, 4, 2,
                            3, 6, 4, 9 };
    int size = arr.Length;
 
    // Function call
    maxLength(arr, size);
}
}
 
// This code is contributed by sanjoy_62

<script>
 
// Javascript Program to implement
// the above approach
 
// Function that print maximum length
// of array
function maxLength(arr, n)
{
       
    // dp[] array to store the
    // maximum length
    let dp = [];
    for(let i = 1; i < n; i++)
    {
        dp[i] = 1;
    }
   
    for(let i = n - 1; i > 1; i--)
    {
           
        // Find all divisors of i
        for(let j = 1;
                j <= Math.sqrt(i); j++)
        {
            if (i % j == 0)
            {
                let s = i / j;
                if (s == j)
                {
                       
                    // If the current value
                    // is greater than the
                    // divisor's value
                    if (arr[i] > arr[s])
                    {
                        dp[s] = Math.max(dp[i] + 1,
                                         dp[s]);
                    }
                }
                else
                {
                       
                    // If current value is greater
                    // than the divisor's value
                    // and s is not equal
                    // to current index
                    if (s != i && arr[i] > arr[s])
                        dp[s] = Math.max(dp[i] + 1,
                                         dp[s]);
       
                    // Condition if current
                    // value is greater
                    // than the divisor's value
                    if (arr[i] > arr[j])
                    {
                        dp[j] = Math.max(dp[i] + 1,
                                         dp[j]);
                    }
                }
            }
        }
    }
    let max = 0;
   
    // Computing the greatest value
    for(let i = 1; i < n; i++)
    {
        if (dp[i] > max)
            max = dp[i];
    }
       
    // Printing maximum length of array
    document.write(max);
}
 
// Driver Code
 
    // Given array arr[]
    let arr = [ 0, 1, 4, 2, 3, 6, 4, 9 ];
    let size = arr.length;
   
    // Function call
    maxLength(arr, size);
     
    // This code is contributed by chinmoy1997pal.
</script>

3

Complejidad de tiempo: O(N*(sqrt(N)) Ya que, para cada índice de la array, calculamos todos sus divisores, esto toma O(sqrt(N))  
Espacio auxiliar: O(N)