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
C++
/* Dynamic Programming implementation of longest bitonic subsequence problem */
#include<stdio.h>
#include<stdlib.h>
/* 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]
*/
int lbs( int arr[], int n )
{
int i, j;
/* Allocate memory for LIS[] and initialize LIS values as 1 for
all indexes */
int *lis = new int[n];
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 */
int *lds = new int [n];
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*/
int 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 program to test above function */
int main()
{
int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5,
13, 3, 11, 7, 15};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of LBS is %d\n", lbs( arr, n ) );
return 0;
}
Java
/* Dynamic Programming implementation in Java for longest bitonic
subsequence problem */
import java.util.*;
import java.lang.*;
import java.io.*;
class LBS
{
/* 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]
*/
static int lbs( int arr[], int n )
{
int i, j;
/* Allocate memory for LIS[] and initialize LIS values as 1 for
all indexes */
int[] lis = new int[n];
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 */
int[] lds = new int [n];
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*/
int 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;
}
public static void main (String[] args)
{
int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5,
13, 3, 11, 7, 15};
int n = arr.length;
System.out.println("Length of LBS is "+ lbs( arr, n ));
}
}
Python3
# 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]
"""
def lbs(arr):
n = len(arr)
# allocate memory for LIS[] and initialize LIS values as 1
# for all indexes
lis = [1 for i in range(n+1)]
# Compute LIS values from left to right
for i in range(1 , n):
for j in range(0 , i):
if ((arr[i] > arr[j]) and (lis[i] < lis[j] +1)):
lis[i] = lis[j] + 1
# allocate memory for LDS and initialize LDS values for
# all indexes
lds = [1 for i in range(n+1)]
# Compute LDS values from right to left
for i in reversed(range(n-1)): #loop from n-2 downto 0
for j in reversed(range(i-1 ,n)): #loop from n-1 downto i-1
if(arr[i] > arr[j] and lds[i] < lds[j] + 1):
lds[i] = lds[j] + 1
# Return the maximum value of (lis[i] + lds[i] - 1)
maximum = lis[0] + lds[0] - 1
for i in range(1 , n):
maximum = max((lis[i] + lds[i]-1), maximum)
return maximum
# Driver program to test the above function
arr = [0 , 8 , 4, 12, 2, 10 , 6 , 14 , 1 , 9 , 5 , 13,
3, 11 , 7 , 15]
print ("Length of LBS is",lbs(arr))
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
/* Dynamic Programming implementation in
C# for longest bitonic subsequence problem */
using System;
class LBS {
/* 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]
*/
static int lbs(int[] arr, int n)
{
int i, j;
/* Allocate memory for LIS[] and initialize
LIS values as 1 for all indexes */
int[] lis = new int[n];
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 */
int[] lds = new int[n];
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*/
int 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
public static void Main()
{
int[] arr = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5,
13, 3, 11, 7, 15 };
int n = arr.Length;
Console.WriteLine("Length of LBS is " + lbs(arr, n));
}
}
// This code is contributed by vt_m.
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
?>
Javascript
<script>
/* Dynamic Programming implementation in JavaScript for 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)
{
let i, j;
/* Allocate memory for LIS[] and initialize LIS values as 1 for
all indexes */
let lis = new Array(n)
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 */
let lds = new Array(n);
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*/
let 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;
}
let arr=[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
let n = arr.length;
document.write("Length of LBS is "+ lbs( arr, n ));
// This code is contributed by avanitrachhadiya2155
</script>
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