Subsecuencia divisoria más larga

Se le da una array A de tamaño N. Su tarea es encontrar la longitud de la subsecuencia divisoria más grande. Una secuencia divisoria es una secuencia a1, a2, …, aN donde ai divide aj siempre que i < j. Por ejemplo, 3, 15, 60, 720 es una secuencia divisoria. 
input: 
la primera línea de cada caso de prueba es N, donde N es el tamaño de la array. 
La segunda línea de cada caso de prueba contiene N enteros separados por espacios, que es la entrada para la array. 
Salida: 
la longitud de los ejemplos de subsecuencias divisorias más grandes 
:

Entrada: arr[] = {2 11 16 12 36 60 71 17 29 144 288 129 432 993} Salida 
: 5 
2 12 36 144 288 está dividiendo la subsecuencia de mayor tamaño
Entrada: 1 2 4 8 16 
Salida: 5 
Toda la secuencia es divisor

Este problema es simplemente una variación de la subsecuencia creciente más larga . Podemos resolver esto usando Programación Dinámica. La idea es encontrar la subsecuencia divisoria más larga que termine con cada elemento y finalmente devolver el máximo de todos.  

/* Dynamic Programming C++ implementation of lds problem */
#include<bits/stdc++.h>
using namespace std;
   
/* lds() returns the length of the longest dividing
  subsequence in arr[] of size n */
int lds( int arr[], int n )
{
    int lds[n];
  
    lds[0] = 1;  
 
    /* Compute optimized lds values in bottom up manner */
    for (int i = 1; i < n; i++ )
    {
        lds[i] = 1;
        for (int j = 0; j < i; j++ ) 
            if (lds[j] != 0 && arr[i] % arr[j] == 0)
                lds[i] = max(lds[i], lds[j] + 1);
    }
 
    // Return maximum value in lds[]
    return *max_element(lds, lds+n);
}
   
/* Driver program to test above function */
int main()
{
    int arr[] = { 2, 11, 16, 12, 36, 60, 71, 17,
                     29, 144, 288, 129, 432, 993};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Length of lds is %d\n", lds( arr, n ) );
    return 0;
}

/* Dynamic Programming Java implementation of lds problem */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG{
/* lds() returns the length of the longest dividing
  subsequence in arr[] of size n */
static int lds( Integer arr[], int n )
{
    Integer lds[]=new Integer[n];
   
    lds[0] = 1;  
  
    /* Compute optimized lds values in bottom up manner */
    for (int i = 1; i < n; i++ )
    {
        lds[i] = 1;
        for (int j = 0; j < i; j++ ) 
            if (lds[j] != 0 && arr[i] % arr[j] == 0)
                lds[i] = Math.max(lds[i], lds[j] + 1);
    }
  
    // Return maximum value in lds[]
    int max=(int)Collections.max(Arrays.asList(lds));
    return max;
}
    
/* Driver program to test above function */
public static void main(String args[])
{
    Integer arr[] = { 2, 11, 16, 12, 36, 60, 71, 17,
                     29, 144, 288, 129, 432, 993};
    int n =arr.length ;
    System.out.println("Length of lds is "+lds( arr, n ) );
}
}

# Dynamic Programming Python3
# implementation of lds problem
 
# lds() returns the length of the longest
# dividing subsequence in arr[] of size n
def lds(arr, n):
     
    lds = [0 for i in range(n)]
     
    lds[0] = 1
     
    # Compute optimized lds values
    # in bottom up manner
    for i in range(n):
        lds[i] = 1
        for j in range(i):
            if (lds[j] != 0 and
                arr[i] % arr[j] == 0):
                lds[i] = max(lds[i], lds[j] + 1)
 
    return max(lds)
 
# Driver Code
arr = [2, 11, 16, 12, 36, 60, 71, 17,
         29, 144, 288, 129, 432, 993]
 
print("Length of lds is",
       lds(arr, len(arr)))
 
# This code is contributed
# by Mohit Kumar

/* Dynamic Programming C# implementation of lds problem */
using System;
using System.Linq;
public class GFG{
    /* lds() returns the length of the longest dividing
      subsequence in arr[] of size n */
    static int lds( int []arr, int n )
    {
        int []lds=new int[n];
 
        lds[0] = 1;  
 
        /* Compute optimized lds values in bottom up manner */
        for (int i = 1; i < n; i++ )
        {
            lds[i] = 1;
            for (int j = 0; j < i; j++ ) 
                if (lds[j] != 0 && arr[i] % arr[j] == 0)
                    lds[i] = Math.Max(lds[i], lds[j] + 1);
        }
 
        // Return maximum value in lds[]
        int max=lds.Max();
        return max;
    }
 
    /* Driver program to test above function */
    public static void Main()
    {
        int []arr = { 2, 11, 16, 12, 36, 60, 71, 17,
                         29, 144, 288, 129, 432, 993};
        int n =arr.Length ;
        Console.Write("Length of lds is "+lds( arr, n ) );
    }
}
 
// This code is contributed by 29AjayKumar

<script>
/* Dynamic Programming Javascript implementation of lds problem */
 
/* lds() returns the length of the longest dividing
  subsequence in arr[] of size n */
function lds(arr,n)
{
    let lds = new Array(n);
    lds[0] = 1; 
   
    /* Compute optimized lds values in bottom up manner */
    for (let i = 1; i < n; i++ )
    {
        lds[i] = 1;
        for (let j = 0; j < i; j++ )
            if (lds[j] != 0 && arr[i] % arr[j] == 0)
                lds[i] = Math.max(lds[i], lds[j] + 1);
    }
   
    // Return maximum value in lds[]
    let max=Math.max(...lds);
    return max;
}
 
/* Driver program to test above function */
let arr=[2, 11, 16, 12, 36, 60, 71, 17,
                     29, 144, 288, 129, 432, 993];
                      
let n =arr.length ;
document.write("Length of lds is "+lds( arr, n ) );
 
// This code is contributed by unknown2108
</script>

Length of lds is 5

Complejidad de tiempo: O(N*N )

Espacio Auxiliar: O(N)