Programa Php para encontrar la subsecuencia bitónica más larga

Dada una array arr[0 … n-1] que contiene n enteros positivos, una subsecuencia de arr[] se llama bitónica si primero es creciente y luego decreciente. Escriba una función que tome una array como argumento y devuelva la longitud de la subsecuencia bitónica más larga. 
Una secuencia ordenada en orden creciente se considera bitónica con la parte decreciente vacía. De manera similar, la secuencia de orden decreciente se considera bitónica con la parte creciente como vacía. 
Ejemplos:

Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
Output: 6 (A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)

Input arr[] = {12, 11, 40, 5, 3, 1}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)

Input arr[] = {80, 60, 30, 40, 20, 10}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)

Fuente: pregunta de la entrevista de Microsoft
 

Solución 
Este problema es una variación del problema estándar de subsecuencia creciente más larga (LIS) . Deje que la array de entrada sea arr[] de longitud n. Necesitamos construir dos arrays lis[] y lds[] usando la solución de programación dinámica del problema LIS . lis[i] almacena la longitud de la subsecuencia creciente más larga que termina en arr[i]. lds[i] almacena la longitud de la subsecuencia decreciente más larga a partir de arr[i]. Finalmente, necesitamos devolver el valor máximo de lis[i] + lds[i] – 1 donde i es de 0 a n-1.
A continuación se muestra la implementación de la solución de programación dinámica anterior. 
 

PHP

<?php 
// Dynamic Programming implementation
// of longest bitonic subsequence problem 
  
/* lbs() returns the length of the Longest 
   Bitonic Subsequence in arr[] of size n. 
   The function mainly creates two temporary 
   arrays lis[] and lds[] and returns the 
   maximum lis[i] + lds[i] - 1.
  
   lis[i] ==> Longest Increasing subsequence
              ending with arr[i]
   lds[i] ==> Longest decreasing subsequence 
              starting with arr[i]
*/
function lbs(&$arr, $n)
{
  
    /* Allocate memory for LIS[] and initialize 
       LIS values as 1 for all indexes */
    $lis = array_fill(0, $n, NULL);
    for ($i = 0; $i < $n; $i++)
        $lis[$i] = 1;
      
    /* Compute LIS values from left to right */
    for ($i = 1; $i < $n; $i++)
        for ($j = 0; $j < $i; $j++)
            if ($arr[$i] > $arr[$j] && 
                $lis[$i] < $lis[$j] + 1)
                $lis[$i] = $lis[$j] + 1;
      
    /* Allocate memory for lds and initialize 
       LDS values for all indexes */
    $lds = array_fill(0, $n, NULL);
    for ($i = 0; $i < $n; $i++)
        $lds[$i] = 1;
      
    /* Compute LDS values from right to left */
    for ($i = $n - 2; $i >= 0; $i--)
        for ($j = $n - 1; $j > $i; $j--)
            if ($arr[$i] > $arr[$j] && 
                $lds[$i] < $lds[$j] + 1)
                $lds[$i] = $lds[$j] + 1;
      
    /* Return the maximum value of 
       lis[i] + lds[i] - 1*/
    $max = $lis[0] + $lds[0] - 1;
    for ($i = 1; $i < $n; $i++)
        if ($lis[$i] + $lds[$i] - 1 > $max)
            $max = $lis[$i] + $lds[$i] - 1;
    return $max;
}
  
// Driver Code
$arr = array(0, 8, 4, 12, 2, 10, 6, 14, 
             1, 9, 5, 13, 3, 11, 7, 15);
$n = sizeof($arr);
echo "Length of LBS is " . lbs( $arr, $n );
  
// This code is contributed by ita_c
?>

Producción: 

 Length of LBS is 7

Complejidad de tiempo: O(n^2) 
Espacio auxiliar: O(n)
 

Consulte el artículo completo sobre la subsecuencia bitónica más larga | DP-15 para más detalles!

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *