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: 3
Explicación: La subsecuencia decreciente más larga es {63, 55, 46}
Entrada: arr[] = {50 , 3, 10, 7, 40, 80}
Salida: 3
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