Dada una array arr[] que contiene n enteros. El problema es encontrar la longitud de la subsecuencia bitónica estricta más larga. Una subsecuencia se llama bitónica estricta si primero es creciente y luego decreciente con la condición de que tanto en la parte creciente como en la decreciente la diferencia absoluta entre los adyacentes sea 1 solamente. 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, 5, 2, 3, 4, 5, 3, 2}
Output : 6
The Longest Strict Bitonic Subsequence is:
{1, 2, 3, 4, 3, 2}.
Input : arr[] = {1, 2, 5, 3, 6, 7, 4, 6, 5}
Output : 5
Método 1: El problema podría resolverse utilizando el concepto de encontrar la subsecuencia bitónica más larga . La única condición que se debe mantener es que los adyacentes tengan una diferencia de 1 solamente. Tiene una complejidad temporal de O(n 2 ).
Método 2 (enfoque eficiente):
La idea es crear dos mapas hash inc y dcr que tengan tuplas en la forma (ele, len) , donde len denota la longitud de la subsecuencia creciente más larga que termina con el elemento ele en el mapa inc y la longitud de la subsecuencia decreciente más larga que comienza con el elemento ele en el mapa dcr respectivamente. También cree dos arrays len_inc[] y len_dcr[] donde len_inc[i] representa la longitud de la subsecuencia creciente más grande que termina con el elemento arr[i] y len_dcr[i]representa la longitud de la subsecuencia decreciente más grande que comienza con el elemento arr[i] . Ahora, para cada elemento arr[i] podemos encontrar la longitud del valor (arr[i]-1) si existe en la tabla hash inc . Sea este valor v (inicialmente v será 0) .
Ahora, la longitud de la subsecuencia creciente más larga que termina en arr[i] sería v+1 . Actualice esta longitud junto con el elemento arr[i] en la tabla hash inc y en la array len_inc[] en el índice i respectivo . Ahora, recorriendo la array de derecha a izquierda, podemos llenar de manera similar la tabla hash dcr y la array len_dcr[] para la subsecuencia decreciente más larga. Finalmente, para cada elemento arr[i] calculamos (len_inc[i] + len_dcr[i] – 1) y devolvemos el valor máximo.
Nota: Aquí, las subsecuencias crecientes y decrecientes solo significan que la diferencia entre elementos adyacentes es solo 1.
Implementación:
C++
// C++ implementation to find length of longest
// strict bitonic subsequence
#include <bits/stdc++.h>
using namespace std;
// function to find length of longest
// strict bitonic subsequence
int longLenStrictBitonicSub(int arr[], int n)
{
// hash table to map the array element with the
// length of the longest subsequence of which
// it is a part of and is the last/first element of
// that subsequence
unordered_map<int, int> inc, dcr;
// arrays to store the length of increasing and
// decreasing subsequences which end at them
// or start from them
int len_inc[n], len_dcr[n];
// to store the length of longest strict
// bitonic subsequence
int longLen = 0;
// traverse the array elements
// from left to right
for (int i=0; i<n; i++)
{
// initialize current length
// for element arr[i] as 0
int len = 0;
// if 'arr[i]-1' is in 'inc'
if (inc.find(arr[i]-1) != inc.end())
len = inc[arr[i]-1];
// update arr[i] subsequence length in 'inc'
// and in len_inc[]
inc[arr[i]] = len_inc[i] = len + 1;
}
// traverse the array elements
// from right to left
for (int i=n-1; i>=0; i--)
{
// initialize current length
// for element arr[i] as 0
int len = 0;
// if 'arr[i]-1' is in 'dcr'
if (dcr.find(arr[i]-1) != dcr.end())
len = dcr[arr[i]-1];
// update arr[i] subsequence length in 'dcr'
// and in len_dcr[]
dcr[arr[i]] = len_dcr[i] = len + 1;
}
// calculating the length of all the strict
// bitonic subsequence
for (int i=0; i<n; i++)
if (longLen < (len_inc[i] + len_dcr[i] - 1))
longLen = len_inc[i] + len_dcr[i] - 1;
// required longest length strict
// bitonic subsequence
return longLen;
}
// Driver program to test above
int main()
{
int arr[] = {1, 5, 2, 3, 4, 5, 3, 2};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Longest length strict bitonic subsequence = "
<< longLenStrictBitonicSub(arr, n);
return 0;
}
Java
// Java implementation to find length of longest
// strict bitonic subsequence
import java.util.*;
class GfG
{
// function to find length of longest
// strict bitonic subsequence
static int longLenStrictBitonicSub(int arr[], int n)
{
// hash table to map the array element with the
// length of the longest subsequence of which
// it is a part of and is the last/first element of
// that subsequence
HashMap<Integer, Integer> inc = new HashMap<Integer, Integer> ();
HashMap<Integer, Integer> dcr = new HashMap<Integer, Integer> ();
// arrays to store the length of increasing and
// decreasing subsequences which end at them
// or start from them
int len_inc[] = new int[n];
int len_dcr[] = new int[n];
// to store the length of longest strict
// bitonic subsequence
int longLen = 0;
// traverse the array elements
// from left to right
for (int i = 0; i < n; i++)
{
// initialize current length
// for element arr[i] as 0
int len = 0;
// if 'arr[i]-1' is in 'inc'
if (inc.containsKey(arr[i] - 1))
len = inc.get(arr[i] - 1);
// update arr[i] subsequence length in 'inc'
// and in len_inc[]
len_inc[i] = len + 1;
inc.put(arr[i], len_inc[i]);
}
// traverse the array elements
// from right to left
for (int i = n - 1; i >= 0; i--)
{
// initialize current length
// for element arr[i] as 0
int len = 0;
// if 'arr[i]-1' is in 'dcr'
if (dcr.containsKey(arr[i] - 1))
len = dcr.get(arr[i] - 1);
// update arr[i] subsequence length in 'dcr'
// and in len_dcr[]
len_dcr[i] = len + 1;
dcr.put(arr[i], len_dcr[i]);
}
// calculating the length of all the strict
// bitonic subsequence
for (int i = 0; i < n; i++)
if (longLen < (len_inc[i] + len_dcr[i] - 1))
longLen = len_inc[i] + len_dcr[i] - 1;
// required longest length strict
// bitonic subsequence
return longLen;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 5, 2, 3, 4, 5, 3, 2};
int n = arr.length;
System.out.println("Longest length strict " +
"bitonic subsequence = " +
longLenStrictBitonicSub(arr, n));
}
}
// This code is contributed by
// prerna saini
Python3
# Python3 implementation to find length of
# longest strict bitonic subsequence
# function to find length of longest
# strict bitonic subsequence
def longLenStrictBitonicSub(arr, n):
# hash table to map the array element
# with the length of the longest subsequence
# of which it is a part of and is the
# last/first element of that subsequence
inc, dcr = dict(), dict()
# arrays to store the length of increasing
# and decreasing subsequences which end at
# them or start from them
len_inc, len_dcr = [0] * n, [0] * n
# to store the length of longest strict
# bitonic subsequence
longLen = 0
# traverse the array elements
# from left to right
for i in range(n):
# initialize current length
# for element arr[i] as 0
len = 0
# if 'arr[i]-1' is in 'inc'
if inc.get(arr[i] - 1) in inc.values():
len = inc.get(arr[i] - 1)
# update arr[i] subsequence length in 'inc'
# and in len_inc[]
inc[arr[i]] = len_inc[i] = len + 1
# traverse the array elements
# from right to left
for i in range(n - 1, -1, -1):
# initialize current length
# for element arr[i] as 0
len = 0
# if 'arr[i]-1' is in 'dcr'
if dcr.get(arr[i] - 1) in dcr.values():
len = dcr.get(arr[i] - 1)
# update arr[i] subsequence length
# in 'dcr' and in len_dcr[]
dcr[arr[i]] = len_dcr[i] = len + 1
# calculating the length of
# all the strict bitonic subsequence
for i in range(n):
if longLen < (len_inc[i] + len_dcr[i] - 1):
longLen = len_inc[i] + len_dcr[i] - 1
# required longest length strict
# bitonic subsequence
return longLen
# Driver Code
if __name__ == "__main__":
arr = [1, 5, 2, 3, 4, 5, 3, 2]
n = len(arr)
print("Longest length strict bitonic subsequence =",
longLenStrictBitonicSub(arr, n))
# This code is contributed by sanjeev2552
C#
// C# implementation to find length of longest
// strict bitonic subsequence
using System;
using System.Collections.Generic;
class GfG
{
// function to find length of longest
// strict bitonic subsequence
static int longLenStrictBitonicSub(int []arr, int n)
{
// hash table to map the array
// element with the length of
// the longest subsequence of
// which it is a part of and
// is the last/first element of
// that subsequence
Dictionary<int, int> inc = new Dictionary<int, int> ();
Dictionary<int, int> dcr = new Dictionary<int, int> ();
// arrays to store the length
// of increasing and decreasing
// subsequences which end at them
// or start from them
int []len_inc = new int[n];
int []len_dcr = new int[n];
// to store the length of longest strict
// bitonic subsequence
int longLen = 0;
// traverse the array elements
// from left to right
for (int i = 0; i < n; i++)
{
// initialize current length
// for element arr[i] as 0
int len = 0;
// if 'arr[i]-1' is in 'inc'
if (inc.ContainsKey(arr[i] - 1))
len = inc[arr[i] - 1];
// update arr[i] subsequence length
// in 'inc' and in len_inc[]
len_inc[i] = len + 1;
if (inc.ContainsKey(arr[i]))
{
inc.Remove(arr[i]);
inc.Add(arr[i], len_inc[i]);
}
else
inc.Add(arr[i], len_inc[i]);
}
// traverse the array elements
// from right to left
for (int i = n - 1; i >= 0; i--)
{
// initialize current length
// for element arr[i] as 0
int len = 0;
// if 'arr[i]-1' is in 'dcr'
if (dcr.ContainsKey(arr[i] - 1))
len = dcr[arr[i] - 1];
// update arr[i] subsequence length in 'dcr'
// and in len_dcr[]
len_dcr[i] = len + 1;
if (dcr.ContainsKey(arr[i]))
{
dcr.Remove(arr[i]);
dcr.Add(arr[i], len_dcr[i]);
}
else
dcr.Add(arr[i], len_dcr[i]);
}
// calculating the length of all the strict
// bitonic subsequence
for (int i = 0; i < n; i++)
if (longLen < (len_inc[i] + len_dcr[i] - 1))
longLen = len_inc[i] + len_dcr[i] - 1;
// required longest length strict
// bitonic subsequence
return longLen;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 5, 2, 3, 4, 5, 3, 2};
int n = arr.Length;
Console.WriteLine("Longest length strict " +
"bitonic subsequence = " +
longLenStrictBitonicSub(arr, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation to find length of longest
// strict bitonic subsequence
// function to find length of longest
// strict bitonic subsequence
function longLenStrictBitonicSub(arr, n)
{
// hash table to map the array element with the
// length of the longest subsequence of which
// it is a part of and is the last/first element of
// that subsequence
var inc = new Map(), dcr = new Map();
// arrays to store the length of increasing and
// decreasing subsequences which end at them
// or start from them
var len_inc = Array(n), len_dcr = Array(n);
// to store the length of longest strict
// bitonic subsequence
var longLen = 0;
// traverse the array elements
// from left to right
for (var i=0; i<n; i++)
{
// initialize current length
// for element arr[i] as 0
var len = 0;
// if 'arr[i]-1' is in 'inc'
if (inc.has(arr[i]-1))
len = inc.get(arr[i]-1);
// update arr[i] subsequence length in 'inc'
// and in len_inc[]
len_inc[i] = len + 1;
inc.set(arr[i], len_inc[i]);
}
// traverse the array elements
// from right to left
for (var i=n-1; i>=0; i--)
{
// initialize current length
// for element arr[i] as 0
var len = 0;
// if 'arr[i]-1' is in 'dcr'
if (dcr.has(arr[i]-1))
len = dcr.get(arr[i]-1);
// update arr[i] subsequence length in 'dcr'
// and in len_dcr[]
len_dcr[i] = len + 1;
dcr.set(arr[i], len_dcr[i]);
}
// calculating the length of all the strict
// bitonic subsequence
for (var i=0; i<n; i++)
if (longLen < (len_inc[i] + len_dcr[i] - 1))
longLen = len_inc[i] + len_dcr[i] - 1;
// required longest length strict
// bitonic subsequence
return longLen;
}
// Driver program to test above
var arr = [1, 5, 2, 3, 4, 5, 3, 2];
var n = arr.length;
document.write( "Longest length strict bitonic subsequence = "
+ longLenStrictBitonicSub(arr, n));
// This code is contributed by itsok.
</script>
Producción
Longest length strict bitonic subsequence = 6
Complejidad temporal: O(n).
Espacio Auxiliar: O(n).
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA