El problema de la subsecuencia bitónica más larga es encontrar la subsecuencia más larga de una secuencia dada de modo que primero sea creciente y luego decreciente. 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: [1, 11, 2, 10, 4, 5, 2, 1]
Output: [1, 2, 10, 4, 2, 1] OR [1, 11, 10, 5, 2, 1]
OR [1, 2, 4, 5, 2, 1]
Input: [12, 11, 40, 5, 3, 1]
Output: [12, 11, 5, 3, 1] OR [12, 40, 5, 3, 1]
Input: [80, 60, 30, 40, 20, 10]
Output: [80, 60, 30, 20, 10] OR [80, 60, 40, 20, 10]
En publicaciones anteriores , hemos discutido sobre el problema de la subsecuencia bitónica más larga. Sin embargo, la publicación solo cubría el código relacionado con la búsqueda de la suma máxima de subsecuencias crecientes, pero no con la construcción de subsecuencias. En esta publicación, discutiremos cómo construir la subsecuencia bitónica más larga.
Sea arr[0..n-1] la array de entrada. Definimos el vector LIS de tal manera que LIS[i] es en sí mismo un vector que almacena la subsecuencia creciente más larga de arr[0..i] que termina en arr[i]. Por lo tanto, para un índice i, LIS[i] puede escribirse recursivamente como –
LIS[0] = {arr[O]}
LIS[i] = {Max(LIS[j])} + arr[i] where j < i and arr[j] < arr[i]
= arr[i], if there is no such j
También definimos un vector LDS tal que LDS[i] es en sí mismo un vector que almacena la subsecuencia decreciente más larga de arr[i..n] que comienza con arr[i]. Por lo tanto, para un índice i, LDS[i] puede escribirse recursivamente como –
LDS[n] = {arr[n]}
LDS[i] = arr[i] + {Max(LDS[j])} where j > i and arr[j] < arr[i]
= arr[i], if there is no such j
Por ejemplo, para array [1 11 2 10 4 5 2 1],
LIS[0]: 1 LIS[1]: 1 11 LIS[2]: 1 2 LIS[3]: 1 2 10 LIS[4]: 1 2 4 LIS[5]: 1 2 4 5 LIS[6]: 1 2 LIS[7]: 1
LDS[0]: 1 LDS[1]: 11 10 5 2 1 LDS[2]: 2 1 LDS[3]: 10 5 2 1 LDS[4]: 4 2 1 LDS[5]: 5 2 1 LDS[6]: 2 1 LDS[7]: 1
Por lo tanto, la subsecuencia bitónica más larga puede ser
LIS[1] + LDS[1] = [1 11 10 5 2 1] OR LIS[3] + LDS[3] = [1 2 10 5 2 1] OR LIS[5] + LDS[5] = [1 2 4 5 2 1]
A continuación se muestra la implementación de la idea anterior:
C++
/* Dynamic Programming solution to print Longest
Bitonic Subsequence */
#include <bits/stdc++.h>
using namespace std;
// Utility function to print Longest Bitonic
// Subsequence
void print(vector<int>& arr, int size)
{
for(int i = 0; i < size; i++)
cout << arr[i] << " ";
}
// Function to construct and print Longest
// Bitonic Subsequence
void printLBS(int arr[], int n)
{
// LIS[i] stores the length of the longest
// increasing subsequence ending with arr[i]
vector<vector<int>> LIS(n);
// initialize LIS[0] to arr[0]
LIS[0].push_back(arr[0]);
// Compute LIS values from left to right
for (int i = 1; i < n; i++)
{
// for every j less than i
for (int j = 0; j < i; j++)
{
if ((arr[j] < arr[i]) &&
(LIS[j].size() > LIS[i].size()))
LIS[i] = LIS[j];
}
LIS[i].push_back(arr[i]);
}
/* LIS[i] now stores Maximum Increasing
Subsequence of arr[0..i] that ends with
arr[i] */
// LDS[i] stores the length of the longest
// decreasing subsequence starting with arr[i]
vector<vector<int>> LDS(n);
// initialize LDS[n-1] to arr[n-1]
LDS[n - 1].push_back(arr[n - 1]);
// Compute LDS values from right to left
for (int i = n - 2; i >= 0; i--)
{
// for every j greater than i
for (int j = n - 1; j > i; j--)
{
if ((arr[j] < arr[i]) &&
(LDS[j].size() > LDS[i].size()))
LDS[i] = LDS[j];
}
LDS[i].push_back(arr[i]);
}
// reverse as vector as we're inserting at end
for (int i = 0; i < n; i++)
reverse(LDS[i].begin(), LDS[i].end());
/* LDS[i] now stores Maximum Decreasing Subsequence
of arr[i..n] that starts with arr[i] */
int max = 0;
int maxIndex = -1;
for (int i = 0; i < n; i++)
{
// Find maximum value of size of LIS[i] + size
// of LDS[i] - 1
if (LIS[i].size() + LDS[i].size() - 1 > max)
{
max = LIS[i].size() + LDS[i].size() - 1;
maxIndex = i;
}
}
// print all but last element of LIS[maxIndex] vector
print(LIS[maxIndex], LIS[maxIndex].size() - 1);
// print all elements of LDS[maxIndex] vector
print(LDS[maxIndex], LDS[maxIndex].size());
}
// Driver program
int main()
{
int arr[] = { 1, 11, 2, 10, 4, 5, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
printLBS(arr, n);
return 0;
}
Java
/* Dynamic Programming solution to print Longest
Bitonic Subsequence */
import java.util.*;
class GFG
{
// Utility function to print Longest Bitonic
// Subsequence
static void print(Vector<Integer> arr, int size)
{
for (int i = 0; i < size; i++)
System.out.print(arr.elementAt(i) + " ");
}
// Function to construct and print Longest
// Bitonic Subsequence
static void printLBS(int[] arr, int n)
{
// LIS[i] stores the length of the longest
// increasing subsequence ending with arr[i]
@SuppressWarnings("unchecked")
Vector<Integer>[] LIS = new Vector[n];
for (int i = 0; i < n; i++)
LIS[i] = new Vector<>();
// initialize LIS[0] to arr[0]
LIS[0].add(arr[0]);
// Compute LIS values from left to right
for (int i = 1; i < n; i++)
{
// for every j less than i
for (int j = 0; j < i; j++)
{
if ((arr[i] > arr[j]) &&
LIS[j].size() > LIS[i].size())
{
for (int k : LIS[j])
if (!LIS[i].contains(k))
LIS[i].add(k);
}
}
LIS[i].add(arr[i]);
}
/*
* LIS[i] now stores Maximum Increasing Subsequence
* of arr[0..i] that ends with arr[i]
*/
// LDS[i] stores the length of the longest
// decreasing subsequence starting with arr[i]
@SuppressWarnings("unchecked")
Vector<Integer>[] LDS = new Vector[n];
for (int i = 0; i < n; i++)
LDS[i] = new Vector<>();
// initialize LDS[n-1] to arr[n-1]
LDS[n - 1].add(arr[n - 1]);
// Compute LDS values from right to left
for (int i = n - 2; i >= 0; i--)
{
// for every j greater than i
for (int j = n - 1; j > i; j--)
{
if (arr[j] < arr[i] &&
LDS[j].size() > LDS[i].size())
for (int k : LDS[j])
if (!LDS[i].contains(k))
LDS[i].add(k);
}
LDS[i].add(arr[i]);
}
// reverse as vector as we're inserting at end
for (int i = 0; i < n; i++)
Collections.reverse(LDS[i]);
/*
* LDS[i] now stores Maximum Decreasing Subsequence
* of arr[i..n] that starts with arr[i]
*/
int max = 0;
int maxIndex = -1;
for (int i = 0; i < n; i++)
{
// Find maximum value of size of
// LIS[i] + size of LDS[i] - 1
if (LIS[i].size() + LDS[i].size() - 1 > max)
{
max = LIS[i].size() + LDS[i].size() - 1;
maxIndex = i;
}
}
// print all but last element of LIS[maxIndex] vector
print(LIS[maxIndex], LIS[maxIndex].size() - 1);
// print all elements of LDS[maxIndex] vector
print(LDS[maxIndex], LDS[maxIndex].size());
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 11, 2, 10, 4, 5, 2, 1 };
int n = arr.length;
printLBS(arr, n);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Dynamic Programming solution to print Longest # Bitonic Subsequence def _print(arr: list, size: int): for i in range(size): print(arr[i], end=" ") # Function to construct and print Longest # Bitonic Subsequence def printLBS(arr: list, n: int): # LIS[i] stores the length of the longest # increasing subsequence ending with arr[i] LIS = [0] * n for i in range(n): LIS[i] = [] # initialize LIS[0] to arr[0] LIS[0].append(arr[0]) # Compute LIS values from left to right for i in range(1, n): # for every j less than i for j in range(i): if ((arr[j] < arr[i]) and (len(LIS[j]) > len(LIS[i]))): LIS[i] = LIS[j].copy() LIS[i].append(arr[i]) # LIS[i] now stores Maximum Increasing # Subsequence of arr[0..i] that ends with # arr[i] # LDS[i] stores the length of the longest # decreasing subsequence starting with arr[i] LDS = [0] * n for i in range(n): LDS[i] = [] # initialize LDS[n-1] to arr[n-1] LDS[n - 1].append(arr[n - 1]) # Compute LDS values from right to left for i in range(n - 2, -1, -1): # for every j greater than i for j in range(n - 1, i, -1): if ((arr[j] < arr[i]) and (len(LDS[j]) > len(LDS[i]))): LDS[i] = LDS[j].copy() LDS[i].append(arr[i]) # reverse as vector as we're inserting at end for i in range(n): LDS[i] = list(reversed(LDS[i])) # LDS[i] now stores Maximum Decreasing Subsequence # of arr[i..n] that starts with arr[i] max = 0 maxIndex = -1 for i in range(n): # Find maximum value of size of LIS[i] + size # of LDS[i] - 1 if (len(LIS[i]) + len(LDS[i]) - 1 > max): max = len(LIS[i]) + len(LDS[i]) - 1 maxIndex = i # print all but last element of LIS[maxIndex] vector _print(LIS[maxIndex], len(LIS[maxIndex]) - 1) # print all elements of LDS[maxIndex] vector _print(LDS[maxIndex], len(LDS[maxIndex])) # Driver Code if __name__ == "__main__": arr = [1, 11, 2, 10, 4, 5, 2, 1] n = len(arr) printLBS(arr, n) # This code is contributed by # sanjeev2552
C#
/* Dynamic Programming solution to print longest
Bitonic Subsequence */
using System;
using System.Linq;
using System.Collections.Generic;
class GFG
{
// Utility function to print longest Bitonic
// Subsequence
static void print(List<int> arr, int size)
{
for (int i = 0; i < size; i++)
Console.Write(arr[i] + " ");
}
// Function to construct and print longest
// Bitonic Subsequence
static void printLBS(int[] arr, int n)
{
// LIS[i] stores the length of the longest
// increasing subsequence ending with arr[i]
List<int>[] LIS = new List<int>[n];
for (int i = 0; i < n; i++)
LIS[i] = new List<int>();
// initialize LIS[0] to arr[0]
LIS[0].Add(arr[0]);
// Compute LIS values from left to right
for (int i = 1; i < n; i++)
{
// for every j less than i
for (int j = 0; j < i; j++)
{
if ((arr[i] > arr[j]) &&
LIS[j].Count > LIS[i].Count)
{
foreach (int k in LIS[j])
if (!LIS[i].Contains(k))
LIS[i].Add(k);
}
}
LIS[i].Add(arr[i]);
}
/*
* LIS[i] now stores Maximum Increasing Subsequence
* of arr[0..i] that ends with arr[i]
*/
// LDS[i] stores the length of the longest
// decreasing subsequence starting with arr[i]
List<int>[] LDS = new List<int>[n];
for (int i = 0; i < n; i++)
LDS[i] = new List<int>();
// initialize LDS[n-1] to arr[n-1]
LDS[n - 1].Add(arr[n - 1]);
// Compute LDS values from right to left
for (int i = n - 2; i >= 0; i--)
{
// for every j greater than i
for (int j = n - 1; j > i; j--)
{
if (arr[j] < arr[i] &&
LDS[j].Count > LDS[i].Count)
foreach (int k in LDS[j])
if (!LDS[i].Contains(k))
LDS[i].Add(k);
}
LDS[i].Add(arr[i]);
}
// reverse as vector as we're inserting at end
for (int i = 0; i < n; i++)
LDS[i].Reverse();
/*
* LDS[i] now stores Maximum Decreasing Subsequence
* of arr[i..n] that starts with arr[i]
*/
int max = 0;
int maxIndex = -1;
for (int i = 0; i < n; i++)
{
// Find maximum value of size of
// LIS[i] + size of LDS[i] - 1
if (LIS[i].Count + LDS[i].Count - 1 > max)
{
max = LIS[i].Count + LDS[i].Count - 1;
maxIndex = i;
}
}
// print all but last element of LIS[maxIndex] vector
print(LIS[maxIndex], LIS[maxIndex].Count - 1);
// print all elements of LDS[maxIndex] vector
print(LDS[maxIndex], LDS[maxIndex].Count);
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, 11, 2, 10, 4, 5, 2, 1 };
int n = arr.Length;
printLBS(arr, n);
}
}
// This code is contributed by PrinciRaj1992
Producción:
1 11 10 5 2 1
La complejidad temporal de la solución de programación dinámica anterior es O(n 2 ).
El espacio auxiliar utilizado por el programa es O(n 2 ).
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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