Dada una array arr[] de tamaño N , la tarea es imprimir la subsecuencia bitónica más larga de la array dada.
Nota: Si sale más de una solución, imprime la solución cualquiera.
Ejemplos:
Entrada: arr[] = {1, 11, 2, 10, 4, 5, 2, 1}
Salida: 1 11 10 5 2 1
Explicación:
Todas las subsecuencias bitónicas más largas posibles de la array anterior son {1, 2, 10, 4, 2, 1}, {1, 11, 10, 5, 2, 1}, {1, 2, 4, 5, 2, 1}.
Por lo tanto, imprima cualquiera de ellos para obtener la respuesta.Entrada: arr[] = {80, 60, 30, 40, 20, 10}
Salida: 80 60 30 20 10
Enfoque de programación dinámica con espacio adicional: consulte el artículo anterior para conocer el enfoque de programación dinámica 2D para resolver el problema.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Enfoque de espacio optimizado: el espacio auxiliar utilizado para el enfoque anterior se puede optimizar mediante la programación dinámica 1D . Siga los pasos a continuación para resolver el problema.
- Cree dos arrays lis[] y lds[] para almacenar, en cada índice i , la longitud de las subsecuencias crecientes y decrecientes más largas que terminan con el elemento arr[i] respectivamente.
- Una vez calculado, encuentre el i -ésimo índice que contiene el valor máximo de lis[i] + lds[i] – 1
- Cree res[] para almacenar todos los elementos de la secuencia bitónica más larga en orden decreciente de elementos seguido de orden creciente de elementos.
- Imprime la array res[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the longest
// bitonic subsequence
void printRes(vector<int>& res)
{
int n = res.size();
for (int i = 0; i < n; i++) {
cout << res[i] << " ";
}
}
// Function to generate the longest
// bitonic subsequence
void printLBS(int arr[], int N)
{
// Store the lengths of LIS
// ending at every index
int lis[N];
// Store the lengths of LDS
// ending at every index
int lds[N];
for (int i = 0; i < N; i++) {
lis[i] = lds[i] = 1;
}
// Compute LIS for all indices
for (int i = 0; i < N; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
if (lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
}
}
}
// Compute LDS for all indices
for (int i = N - 1; i >= 0; i--) {
for (int j = N - 1; j > i; j--) {
if (arr[j] < arr[i]) {
if (lds[i] < lds[j] + 1)
lds[i] = lds[j] + 1;
}
}
}
// Find the index having
// maximum value of
// lis[i] + lds[i] - 1
int MaxVal = arr[0], inx = 0;
for (int i = 0; i < N; i++) {
if (MaxVal < lis[i] + lds[i] - 1) {
MaxVal = lis[i] + lds[i] - 1;
inx = i;
}
}
// Stores the count of elements in
// increasing order in Bitonic subsequence
int ct1 = lis[inx];
vector<int> res;
// Store the increasing subsequence
for (int i = inx; i >= 0 && ct1 > 0; i--) {
if (lis[i] == ct1) {
res.push_back(arr[i]);
ct1--;
}
}
// Sort the bitonic subsequence
// to arrange smaller elements
// at the beginning
reverse(res.begin(), res.end());
// Stores the count of elements in
// decreasing order in Bitonic subsequence
int ct2 = lds[inx] - 1;
for (int i = inx; i < N && ct2 > 0; i++) {
if (lds[i] == ct2) {
res.push_back(arr[i]);
ct2--;
}
}
// Print the longest
// bitonic sequence
printRes(res);
}
// Driver Code
int main()
{
int arr[] = { 80, 60, 30, 40, 20, 10 };
int N = sizeof(arr) / sizeof(arr[0]);
printLBS(arr, N);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG {
// Function to print the longest
// bitonic subsequence
static void printRes(Vector<Integer> res)
{
Enumeration enu = res.elements();
while (enu.hasMoreElements())
{
System.out.print(enu.nextElement() + " ");
}
}
// Function to generate the longest
// bitonic subsequence
static void printLBS(int arr[], int N)
{
// Store the lengths of LIS
// ending at every index
int lis[] = new int[N];
// Store the lengths of LDS
// ending at every index
int lds[] = new int[N];
for(int i = 0; i < N; i++)
{
lis[i] = lds[i] = 1;
}
// Compute LIS for all indices
for(int i = 0; i < N; i++)
{
for(int j = 0; j < i; j++)
{
if (arr[j] < arr[i])
{
if (lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
}
}
}
// Compute LDS for all indices
for(int i = N - 1; i >= 0; i--)
{
for(int j = N - 1; j > i; j--)
{
if (arr[j] < arr[i])
{
if (lds[i] < lds[j] + 1)
lds[i] = lds[j] + 1;
}
}
}
// Find the index having
// maximum value of
// lis[i] + lds[i] - 1
int MaxVal = arr[0], inx = 0;
for(int i = 0; i < N; i++)
{
if (MaxVal < lis[i] + lds[i] - 1)
{
MaxVal = lis[i] + lds[i] - 1;
inx = i;
}
}
// Stores the count of elements in
// increasing order in Bitonic subsequence
int ct1 = lis[inx];
Vector<Integer> res = new Vector<Integer>();
// Store the increasing subsequence
for(int i = inx; i >= 0 && ct1 > 0; i--)
{
if (lis[i] == ct1)
{
res.add(arr[i]);
ct1--;
}
}
// Sort the bitonic subsequence
// to arrange smaller elements
// at the beginning
Collections.reverse(res);
// Stores the count of elements in
// decreasing order in Bitonic subsequence
int ct2 = lds[inx] - 1;
for(int i = inx; i < N && ct2 > 0; i++)
{
if (lds[i] == ct2)
{
res.add(arr[i]);
ct2--;
}
}
// Print the longest
// bitonic sequence
printRes(res);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 80, 60, 30, 40, 20, 10 };
int N = arr.length;
printLBS(arr, N);
}
}
// This code is contributed by chitranayal
Python3
# Python3 program to implement # the above approach # Function to print the longest # bitonic subsequence def printRes(res): n = len(res) for i in range(n): print(res[i], end = " ") # Function to generate the longest # bitonic subsequence def printLBS(arr, N): # Store the lengths of LIS # ending at every index lis = [0] * N # Store the lengths of LDS # ending at every index lds = [0] * N for i in range(N): lis[i] = lds[i] = 1 # Compute LIS for all indices for i in range(N): for j in range(i): if arr[j] < arr[i]: if lis[i] < lis[j] + 1: lis[i] = lis[j] + 1 # Compute LDS for all indices for i in range(N - 1, -1, -1): for j in range(N - 1, i, -1): if arr[j] < arr[i]: if lds[i] < lds[j] + 1: lds[i] = lds[j] + 1 # Find the index having # maximum value of # lis[i]+lds[i]+1 MaxVal = arr[0] inx = 0 for i in range(N): if MaxVal < lis[i] + lds[i] - 1: MaxVal = lis[i] + lds[i] - 1 inx = i # Stores the count of elements in # increasing order in Bitonic subsequence ct1 = lis[inx] res = [] i = inx # Store the increasing subsequence while i >= 0 and ct1 > 0: if lis[i] == ct1: res.append(arr[i]) ct1 -= 1 i -= 1 # Sort the bitonic subsequence # to arrange smaller elements # at the beginning res.reverse() # Stores the count of elements in # decreasing order in Bitonic subsequence ct2 = lds[inx] - 1 i = inx while i < N and ct2 > 0: if lds[i] == ct2: res.append(arr[i]) ct2 -= 1 i += 1 # Print the longest # bitonic sequence printRes(res) # Driver code arr = [ 80, 60, 30, 40, 20, 10 ] N = len(arr) printLBS(arr, N) # This code is contributed by Stuti Pathak
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print the longest
// bitonic subsequence
static void printRes(List<int> res)
{
foreach(int enu in res)
{
Console.Write(enu + " ");
}
}
// Function to generate the longest
// bitonic subsequence
static void printLBS(int[] arr, int N)
{
// Store the lengths of LIS
// ending at every index
int[] lis = new int[N];
// Store the lengths of LDS
// ending at every index
int[] lds = new int[N];
for (int i = 0; i < N; i++)
{
lis[i] = lds[i] = 1;
}
// Compute LIS for all indices
for (int i = 0; i < N; i++)
{
for (int j = 0; j < i; j++)
{
if (arr[j] < arr[i])
{
if (lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
}
}
}
// Compute LDS for all indices
for (int i = N - 1; i >= 0; i--)
{
for (int j = N - 1; j > i; j--)
{
if (arr[j] < arr[i])
{
if (lds[i] < lds[j] + 1)
lds[i] = lds[j] + 1;
}
}
}
// Find the index having
// maximum value of
// lis[i] + lds[i] - 1
int MaxVal = arr[0], inx = 0;
for (int i = 0; i < N; i++)
{
if (MaxVal < lis[i] + lds[i] - 1)
{
MaxVal = lis[i] + lds[i] - 1;
inx = i;
}
}
// Stores the count of elements in
// increasing order in Bitonic subsequence
int ct1 = lis[inx];
List<int> res = new List<int>();
// Store the increasing subsequence
for (int i = inx; i >= 0 && ct1 > 0; i--)
{
if (lis[i] == ct1)
{
res.Add(arr[i]);
ct1--;
}
}
// Sort the bitonic subsequence
// to arrange smaller elements
// at the beginning
res.Reverse();
// Stores the count of elements in
// decreasing order in Bitonic subsequence
int ct2 = lds[inx] - 1;
for (int i = inx; i < N && ct2 > 0; i++)
{
if (lds[i] == ct2)
{
res.Add(arr[i]);
ct2--;
}
}
// Print the longest
// bitonic sequence
printRes(res);
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = {80, 60, 30, 40, 20, 10};
int N = arr.Length;
printLBS(arr, N);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to print the longest
// bitonic subsequence
function printRes( res)
{
var n = res.length;
for (var i = 0; i < n; i++) {
document.write( res[i] + " ");
}
}
// Function to generate the longest
// bitonic subsequence
function printLBS(arr, N)
{
// Store the lengths of LIS
// ending at every index
var lis = Array(N);
// Store the lengths of LDS
// ending at every index
var lds = Array(N);
for (var i = 0; i < N; i++) {
lis[i] = lds[i] = 1;
}
// Compute LIS for all indices
for (var i = 0; i < N; i++) {
for (var j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
if (lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
}
}
}
// Compute LDS for all indices
for (var i = N - 1; i >= 0; i--) {
for (var j = N - 1; j > i; j--) {
if (arr[j] < arr[i]) {
if (lds[i] < lds[j] + 1)
lds[i] = lds[j] + 1;
}
}
}
// Find the index having
// maximum value of
// lis[i] + lds[i] - 1
var MaxVal = arr[0], inx = 0;
for (var i = 0; i < N; i++) {
if (MaxVal < lis[i] + lds[i] - 1) {
MaxVal = lis[i] + lds[i] - 1;
inx = i;
}
}
// Stores the count of elements in
// increasing order in Bitonic subsequence
var ct1 = lis[inx];
var res = [];
// Store the increasing subsequence
for (var i = inx; i >= 0 && ct1 > 0; i--) {
if (lis[i] == ct1) {
res.push(arr[i]);
ct1--;
}
}
// Sort the bitonic subsequence
// to arrange smaller elements
// at the beginning
res.reverse();
// Stores the count of elements in
// decreasing order in Bitonic subsequence
var ct2 = lds[inx] - 1;
for (var i = inx; i < N && ct2 > 0; i++) {
if (lds[i] == ct2) {
res.push(arr[i]);
ct2--;
}
}
// Print the longest
// bitonic sequence
printRes(res);
}
// Driver Code
var arr = [80, 60, 30, 40, 20, 10];
var N = arr.length;
printLBS(arr, N);
</script>
Producción:
80 60 30 20 10
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por helloween123 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA