Subsecuencia decreciente más larga

Dada una array de N enteros, encuentre la longitud de la subsecuencia más larga de una secuencia dada de modo que todos los elementos de la subsecuencia se clasifiquen en orden estrictamente decreciente. 

Ejemplos:  

Entrada: arr[] = [15, 27, 14, 38, 63, 55, 46, 65, 85] 
Salida:
Explicación: La subsecuencia decreciente más larga es {63, 55, 46} 
Entrada: arr[] = {50 , 3, 10, 7, 40, 80} 
Salida:
Explicación: La subsecuencia decreciente más larga es {50, 10, 7} 

El problema se puede resolver usando la Subestructura Óptima  de Programación Dinámica : Sea arr[0…n-1] la array de entrada y lds[i] la longitud de la LDS que termina en el índice i tal que arr[i] es el último elemento de el SUD. Entonces, lds[i] puede escribirse recursivamente como: 

lds[i] = 1 + max(lds[j]) donde i > j > 0 y arr[j] > arr[i] o 
lds[i] = 1, si no existe tal j.

Para encontrar el LDS para una array determinada, debemos devolver max(lds[i]) donde n > i > 0.  

C++

// CPP program to find the length of the
// longest decreasing subsequence
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns the length
// of the longest decreasing subsequence
int lds(int arr[], int n)
{
    int lds[n];
    int i, j, max = 0;
 
    // Initialize LDS with 1 for all index
    // The minimum LDS starting with any
    // element is always 1
    for (i = 0; i < n; i++)
        lds[i] = 1;
 
    // Compute LDS from every index
    // in bottom up manner
    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (arr[i] < arr[j] && lds[i] < lds[j] + 1)
                lds[i] = lds[j] + 1;
 
    // Select the maximum
    // of all the LDS values
    for (i = 0; i < n; i++)
        if (max < lds[i])
            max = lds[i];
 
    // returns the length of the LDS
    return max;
}
// Driver Code
int main()
{
    int arr[] = { 15, 27, 14, 38, 63, 55, 46, 65, 85 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of LDS is " << lds(arr, n);
    return 0;
}

Java

// Java program to find the
// length of the longest
// decreasing subsequence
import java.io.*;
 
class GFG
{
 
// Function that returns the
// length of the longest
// decreasing subsequence
static int lds(int arr[], int n)
{
    int lds[] = new int[n];
    int i, j, max = 0;
 
    // Initialize LDS with 1
    // for all index. The minimum
    // LDS starting with any
    // element is always 1
    for (i = 0; i < n; i++)
        lds[i] = 1;
 
    // Compute LDS from every
    // index in bottom up manner
    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (arr[i] < arr[j] &&
                         lds[i] < lds[j] + 1)
                lds[i] = lds[j] + 1;
 
    // Select the maximum
    // of all the LDS values
    for (i = 0; i < n; i++)
        if (max < lds[i])
            max = lds[i];
 
    // returns the length
    // of the LDS
    return max;
}
// Driver Code
public static void main (String[] args)
{
    int arr[] = { 15, 27, 14, 38,
                  63, 55, 46, 65, 85 };
    int n = arr.length;
    System.out.print("Length of LDS is " +
                             lds(arr, n));
}
}
 
// This code is contributed by anuj_67.

Python 3

# Python 3 program to find the length of
# the longest decreasing subsequence
 
# Function that returns the length
# of the longest decreasing subsequence
def lds(arr, n):
 
    lds = [0] * n
    max = 0
 
    # Initialize LDS with 1 for all index
    # The minimum LDS starting with any
    # element is always 1
    for i in range(n):
        lds[i] = 1
 
    # Compute LDS from every index
    # in bottom up manner
    for i in range(1, n):
        for j in range(i):
            if (arr[i] < arr[j] and
                lds[i] < lds[j] + 1):
                lds[i] = lds[j] + 1
 
    # Select the maximum
    # of all the LDS values
    for i in range(n):
        if (max < lds[i]):
            max = lds[i]
 
    # returns the length of the LDS
    return max
 
# Driver Code
if __name__ == "__main__":
     
    arr = [ 15, 27, 14, 38,
            63, 55, 46, 65, 85 ]
    n = len(arr)
    print("Length of LDS is", lds(arr, n))
 
# This code is contributed by ita_c

C#

// C# program to find the
// length of the longest
// decreasing subsequence
using System;
 
class GFG
{
 
// Function that returns the
// length of the longest
// decreasing subsequence
static int lds(int []arr, int n)
{
    int []lds = new int[n];
    int i, j, max = 0;
 
    // Initialize LDS with 1
    // for all index. The minimum
    // LDS starting with any
    // element is always 1
    for (i = 0; i < n; i++)
        lds[i] = 1;
 
    // Compute LDS from every
    // index in bottom up manner
    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (arr[i] < arr[j] &&
                        lds[i] < lds[j] + 1)
                lds[i] = lds[j] + 1;
 
    // Select the maximum
    // of all the LDS values
    for (i = 0; i < n; i++)
        if (max < lds[i])
            max = lds[i];
 
    // returns the length
    // of the LDS
    return max;
}
// Driver Code
public static void Main ()
{
    int []arr = { 15, 27, 14, 38,
                63, 55, 46, 65, 85 };
    int n = arr.Length;
    Console.Write("Length of LDS is " +
                          lds(arr, n));
}
}
 
// This code is contributed by anuj_67.

PHP

<?php
// PHP program to find the
// length of the longest
// decreasing subsequence
 
 
// Function that returns the
// length of the longest
// decreasing subsequence
function lds($arr, $n)
{
    $lds = array();
    $i; $j; $max = 0;
 
    // Initialize LDS with 1
    // for all index The minimum
    // LDS starting with any
    // element is always 1
    for ($i = 0; $i < $n; $i++)
        $lds[$i] = 1;
 
    // Compute LDS from every
    // index in bottom up manner
    for ($i = 1; $i < $n; $i++)
        for ($j = 0; $j < $i; $j++)
            if ($arr[$i] < $arr[$j] and
                $lds[$i] < $lds[$j] + 1)
                {
                    $lds[$i] = $lds[$j] + 1;
                }
 
    // Select the maximum
    // of all the LDS values
    for ($i = 0; $i < $n; $i++)
        if ($max < $lds[$i])
            $max = $lds[$i];
 
    // returns the length
    // of the LDS
    return $max;
}
 
// Driver Code
$arr = array(15, 27, 14, 38, 63,
             55, 46, 65, 85);
$n = count($arr);
echo "Length of LDS is " ,
            lds($arr, $n);
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
// Javascript program to find the
// length of the longest
// decreasing subsequence
     
    // Function that returns the
// length of the longest
// decreasing subsequence
    function lds(arr,n)
    {
        let lds = new Array(n);
    let i, j, max = 0;
   
    // Initialize LDS with 1
    // for all index. The minimum
    // LDS starting with any
    // element is always 1
    for (i = 0; i < n; i++)
        lds[i] = 1;
   
    // Compute LDS from every
    // index in bottom up manner
    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (arr[i] < arr[j] &&
                         lds[i] < lds[j] + 1)
                lds[i] = lds[j] + 1;
   
    // Select the maximum
    // of all the LDS values
    for (i = 0; i < n; i++)
        if (max < lds[i])
            max = lds[i];
   
    // returns the length
    // of the LDS
    return max;
    }
     
    // Driver Code
    let arr=[15, 27, 14, 38,
                  63, 55, 46, 65, 85 ];
     
    let n = arr.length;
    document.write("Length of LDS is " +
                             lds(arr, n));
     
     
    // This code is contributed by rag2127
</script>
Producción : 

Length of LDS is 3

 

Complejidad de tiempo : O(n 2
Espacio auxiliar : O(n)
Artículo relacionado : https://www.geeksforgeeks.org/longest-increasing-subsequence/
 

Publicación traducida automáticamente

Artículo escrito por aganjali10 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 *