Longitud de la subsecuencia de división de índice creciente más larga

Dada una array arr[] de tamaño N , la tarea es encontrar la subsecuencia creciente más larga tal que el índice de cualquier elemento sea divisible por el índice del elemento anterior (LIIDS). Las siguientes son las condiciones necesarias para el LIIDS:
Si i, j son dos índices en la array dada. Después: 
 

• yo <j
• j % yo = 0
• arr[yo] < arr[j]

Ejemplos: 
 

Entrada: arr[] = {1, 2, 3, 7, 9, 10} 
Salida: 3 
Explicación: 
La subsecuencia = {1, 2, 7} 
Índices de los elementos de la subsecuencia = {1, 2, 4} 
Condición de índices: 
2 es divisible por 1 
4 es divisible por 2 
O 
Otra posible subsecuencia = {1, 3, 10} 
Índices de elementos de subsecuencia = {1, 3, 6} 
Condición de índices: 
3 es divisible por 1 
6 es divisible por 3
Entrada: arr[] = {7, 1, 3, 4, 6} 
Salida: 2 
Explicación: 
La subsecuencia = {1, 4} 
Índices de elementos de la subsecuencia = {2, 4} 
Condición de los índices: 
4 es divisible por 2 
 

Enfoque: La idea es utilizar el concepto de programación Dinámica para resolver este problema. 
 

• Cree primero una array dp[] e inicialice la array con 1. Esto se debe a que la longitud mínima de la subsecuencia divisoria es 1.
• Ahora, para cada índice ‘i’ en la array, incremente el conteo de los valores en los índices en todos sus múltiplos.
• Finalmente, cuando el paso anterior se realiza para todos los valores, el valor máximo presente en la array es la respuesta requerida.

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

// C++ program to find the length of
// the longest increasing sub-sequence
// such that the index of the element is
// divisible by index of previous element
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of
// the longest increasing sub-sequence
// such that the index of the element is
// divisible by index of previous element
int LIIDS(int arr[], int N)
{
    // Initialize the dp[] array with 1 as a
    // single element will be of 1 length
    int dp[N + 1];
 
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        dp[i] = 1;
    }
 
    // Traverse the given array
    for (int i = 1; i <= N; i++) {
 
        // If the index is divisible by
        // the previous index
        for (int j = i + i; j <= N; j += i) {
 
            // if increasing
            // subsequence identified
            if (arr[j] > arr[i]) {
                dp[j] = max(dp[j], dp[i] + 1);
            }
        }
 
        // Longest length is stored
        ans = max(ans, dp[i]);
    }
    return ans;
}
 
// Driver code
int main()
{
 
    int arr[] = { 1, 2, 3, 7, 9, 10 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << LIIDS(arr, N);
    return 0;
}

// Java program to find the length of
// the longest increasing sub-sequence
// such that the index of the element is
// divisible by index of previous element
import java.util.*;
 
class GFG{
 
// Function to find the length of
// the longest increasing sub-sequence
// such that the index of the element is
// divisible by index of previous element
static int LIIDS(int arr[], int N)
{
 
    // Initialize the dp[] array with 1 as a
    // single element will be of 1 length
    int[] dp = new int[N + 1];
    int ans = 0;
     
    for(int i = 1; i <= N; i++)
    {
       dp[i] = 1;
    }
 
    // Traverse the given array
    for(int i = 1; i <= N; i++)
    {
         
       // If the index is divisible by
       // the previous index
       for(int j = i + i; j <= N; j += i)
       {
            
          // If increasing
          // subsequence identified
          if (j < arr.length && arr[j] > arr[i])
          {
              dp[j] = Math.max(dp[j], dp[i] + 1);
          }
       }
        
       // Longest length is stored
       ans = Math.max(ans, dp[i]);
    }
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 1, 2, 3, 7, 9, 10 };
    int N = arr.length;
 
    System.out.println(LIIDS(arr, N));
}
}
 
// This code is contributed by AbhiThakur

# Python3 program to find the length of
# the longest increasing sub-sequence
# such that the index of the element is
# divisible by index of previous element
 
# Function to find the length of
# the longest increasing sub-sequence
# such that the index of the element is
# divisible by index of previous element
def LIIDS(arr, N):
     
    # Initialize the dp[] array with 1 as a
    # single element will be of 1 length
    dp = []
    for i in range(1, N + 1):
        dp.append(1)
     
    ans = 0
     
    # Traverse the given array
    for i in range(1, N + 1):
         
        # If the index is divisible by
        # the previous index
        j = i + i
        while j <= N:
             
            # If increasing
            # subsequence identified
            if j < N and i < N and arr[j] > arr[i]:
                dp[j] = max(dp[j], dp[i] + 1)
             
            j += i
             
        # Longest length is stored
        if i < N:
            ans = max(ans, dp[i])
         
    return ans
 
# Driver code
arr = [ 1, 2, 3, 7, 9, 10 ]
 
N = len(arr)
 
print(LIIDS(arr, N))
 
# This code is contributed by ishayadav181

// C# program to find the length of
// the longest increasing sub-sequence
// such that the index of the element is
// divisible by index of previous element
using System;
 
class GFG{
 
// Function to find the length of
// the longest increasing sub-sequence
// such that the index of the element is
// divisible by index of previous element
static int LIIDS(int[] arr, int N)
{
 
    // Initialize the dp[] array with 1 as a
    // single element will be of 1 length
    int[] dp = new int[N + 1];
    int ans = 0;
     
    for(int i = 1; i <= N; i++)
    {
        dp[i] = 1;
    }
 
    // Traverse the given array
    for(int i = 1; i <= N; i++)
    {
         
        // If the index is divisible by
        // the previous index
        for(int j = i + i; j <= N; j += i)
        {
             
            // If increasing
            // subsequence identified
            if (j < arr.Length && arr[j] > arr[i])
            {
                dp[j] = Math.Max(dp[j], dp[i] + 1);
            }
        }
         
        // Longest length is stored
        ans = Math.Max(ans, dp[i]);
    }
    return ans;
}
 
// Driver code
public static void Main()
{
    int[] arr = new int[] { 1, 2, 3, 7, 9, 10 };
    int N = arr.Length;
 
    Console.WriteLine(LIIDS(arr, N));
}
}
 
// This code is contributed by sanjoy_62

<script>
     
// Javascript program to find the length of
// the longest increasing sub-sequence
// such that the index of the element is
// divisible by index of previous element
 
// Function to find the length of
// the longest increasing sub-sequence
// such that the index of the element is
// divisible by index of previous element
function LIIDS(arr, N)
{
   
    // Initialize the dp[] array with 1 as a
    // single element will be of 1 length
    let dp = [];
    let ans = 0;
       
    for(let i = 1; i <= N; i++)
    {
       dp[i] = 1;
    }
   
    // Traverse the given array
    for(let i = 1; i <= N; i++)
    {
           
       // If the index is divisible by
       // the previous index
       for(let j = i + i; j <= N; j += i)
       {
              
          // If increasing
          // subsequence identified
          if (j < arr.length && arr[j] > arr[i])
          {
              dp[j] = Math.max(dp[j], dp[i] + 1);
          }
       }
          
       // Longest length is stored
       ans = Math.max(ans, dp[i]);
    }
    return ans;
}
     
// Driver code
 
    let arr = [ 1, 2, 3, 7, 9, 10 ];
    let N = arr.length;
   
    document.write(LIIDS(arr, N));
 
// This code is contributed by susmitakundugoaldanga.
</script>

3

Complejidad de tiempo: O(N log(N)) , donde N es la longitud de la array.