Dada una array arr[] de enteros positivos de tamaño N , la tarea es encontrar el producto máximo de la subsecuencia bitónica de tamaño 3.
Subsecuencia bitónica: subsecuencia en la que los elementos están primero en orden creciente y luego en orden decreciente. Los elementos en la subsecuencia siguen este orden arr[i] < arr[j] > arr[k] para i < j < k donde i, j, k son el índice de la array dada.
Nota: Si no se encuentra dicho elemento, imprima -1.
Ejemplos:
Entrada: arr[] = {1, 8, 3, 7, 5, 6, 7}
Salida: 126
Explicación:
Las subsecuencias bitónicas de tamaño 3 son
{1, 8, 3}, {1, 8, 7}, {1 , 8, 5}, {1, 8, 6}, {1, 7, 6}, {3, 7, 6}, {1, 7, 5}, {3, 7, 5}.
Por lo tanto, el producto máximo de la subsecuencia bitónica es 3*7*6 = 126Entrada: arr[] = {1, 8, 3, 7}
Salida: 56
Explicación:
Las subsecuencias bitónicas de tamaño 3 son
{1, 8, 3}, {1, 8, 7}, {1, 7, 3}.
Por lo tanto, el producto máximo de la subsecuencia bitónica es 1*8*7 = 56
Enfoque ingenuo: una solución simple es encontrar el producto de todas las subsecuencias bitónicas de tamaño 3 y tomar el máximo entre ellas.
Algoritmo:
- Inicialice ans a -1, de modo que si no existe tal subsecuencia, la salida será -1.
- Iterar sobre la array con tres bucles anidados con variables de bucle como i, j y k para elegir tres elementos de la array.
- Verifique si arr[j] > arr[i] y arr[j] > arr[k] luego actualice ans con el valor máximo entre ans y arr[i] * arr[j] * arr[k] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// maximum product of the bitonic
// subsequence of size 3
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum
// product of bitonic subsequence
// of size 3
int maxProduct(int arr[], int n){
// Initialize ans to -1 if no such
// subsequence exist in the array
int ans = -1;
// Nested loops to choose the three
// elements of the array
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
// Condition to check if
// they form a bitonic subsequence
if (arr[i] < arr[j] &&
arr[j] > arr[k])
ans = max(
ans, arr[i] * arr[j] * arr[k]
);
}
}
}
return ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 8, 3, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << maxProduct(arr, n) << endl;
}
Java
// Java implementation to find the
// maximum product of the bitonic
// subsequence of size 3
import java.util.*;
class GFG{
// Function to find the maximum
// product of bitonic subsequence
// of size 3
static int maxProduct(int arr[], int n){
// Initialize ans to -1 if no such
// subsequence exist in the array
int ans = -1;
// Nested loops to choose the three
// elements of the array
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
// Condition to check if
// they form a bitonic subsequence
if (arr[i] < arr[j] &&
arr[j] > arr[k])
ans = Math.max(
ans, arr[i] * arr[j] * arr[k]
);
}
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 8, 3, 7 };
int n = arr.length;
// Function call
System.out.print(maxProduct(arr, n) +"\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation to find the # maximum product of the bitonic # subsequence of size 3 # Function to find the maximum # product of bitonic subsequence # of size 3 def maxProduct(arr, n): # Initialize ans to -1 if no such # subsequence exist in the array ans = -1 # Nested loops to choose the three # elements of the array for i in range(n - 2): for j in range(i + 1, n - 1): for k in range(j + 1, n): # Condition to check if # they form a bitonic subsequence if (arr[i] < arr[j] and arr[j] > arr[k]): ans = max(ans, arr[i] * arr[j] * arr[k]) return ans # Driver Code if __name__ == '__main__': arr= [ 1, 8, 3, 7] n = len(arr) # Function call print(maxProduct(arr, n)) # This code is contributed by mohit kumar 29
C#
// C# implementation to find the
// maximum product of the bitonic
// subsequence of size 3
using System;
class GFG {
// Function to find the maximum
// product of bitonic subsequence
// of size 3
static int maxProduct(int[] arr, int n)
{
// Initialize ans to -1 if no such
// subsequence exist in the array
int ans = -1;
// Nested loops to choose the three
// elements of the array
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
// Condition to check if
// they form a bitonic subsequence
if (arr[i] < arr[j] &&
arr[j] > arr[k])
ans = Math.Max(ans, arr[i] * arr[j] * arr[k]
);
}
}
}
return ans;
}
// Driver code
static void Main()
{
int[] arr = new int[] { 1, 8, 3, 7 };
int n = arr.Length;
// Function call to find product
Console.Write(maxProduct(arr, n));
}
}
// This code is contributed by shubhamsingh
Javascript
<script>
// Java script implementation to find the
// maximum product of the bitonic
// subsequence of size 3
// Function to find the maximum
// product of bitonic subsequence
// of size 3
function maxProduct(arr,n){
// Initialize ans to -1 if no such
// subsequence exist in the array
let ans = -1;
// Nested loops to choose the three
// elements of the array
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
for (let k = j + 1; k < n; k++) {
// Condition to check if
// they form a bitonic subsequence
if (arr[i] < arr[j] &&
arr[j] > arr[k])
ans = Math.max(
ans, arr[i] * arr[j] * arr[k]
);
}
}
}
return ans;
}
// Driver Code
let arr = [ 1, 8, 3, 7 ];
let n = arr.length;
// Function call
document.write(maxProduct(arr, n) +"<br>");
// This code is contributed by Bobby
</script>
Producción:
56
Análisis de rendimiento:
- Complejidad de tiempo: como en el enfoque anterior, hay tres bucles anidados para encontrar el producto máximo de la subsecuencia bitónica de tamaño 3, por lo que la Complejidad de tiempo será O(N 3 ) .
- Espacio auxiliar: como en el enfoque anterior, no se usa espacio adicional, por lo que el espacio auxiliar será O(1) .
Enfoque eficiente: la idea es encontrar el valor más grande en el lado izquierdo y derecho de cada índice, que son más pequeños que el elemento presente en el índice actual, para hacer esto, use un BST de autoequilibrio y luego, para cada elemento, encuentre el producto máximo. que se pueden formar y sacar el máximo partido a esos productos.
Self-Balancing BST se implementa como se establece en C++ y TreeSet en Java .
Algoritmo:
- Declare un BST autoequilibrado (digamos s ).
- Declare dos arrays nuevas left[] y right[] para almacenar el límite inferior de arr[i] a la izquierda de ese elemento en left[i] y el límite inferior de arr[i] a la derecha de ese elemento en right[i].
- Ejecute un ciclo de 0 a length – 1 para encontrar el límite inferior de arr[i] que queda de ese elemento y guárdelo en la izquierda[i].
- Ejecute un ciclo desde la longitud -1 a 0 para encontrar el límite inferior de arr[i] a la derecha de ese elemento y guárdelo en la derecha[i].
- Ejecute un ciclo de 0 a longitud – 1 para encontrar la subsecuencia bitónica que se puede formar usando ese elemento para obtener el producto máximo usando la array izquierda [] y derecha []. Es decir, para cada elemento, la subsecuencia bitónica del producto máximo que se puede formar es left[i] * right[i] * arr[i] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// maximum product of the bitonic
// subsequence of size 3
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum
// product of bitonic subsequence
// of size 3
int maxProduct(int arr[], int n){
// Self Balancing BST
set<int> s;
set<int>::iterator it;
// Left array to store the
// maximum smallest value for
// every element in left of it
int Left[n];
// Right array to store the
// maximum smallest value for
// every element in right of it
int Right[n];
// Loop to find the maximum
// smallest element in left of
// every element in array
for (int i = 0; i < n; i++) {
s.insert(arr[i]);
it = s.lower_bound(arr[i]);
// Condition to check if there
// is a maximum smallest element
if (it != s.begin()) {
it--;
Left[i] = *it;
}
else {
Left[i] = -1;
}
}
// Clear Set
s.clear();
// Loop to find the maximum
// smallest element in right of
// every element in array
for (int i = n - 1; i >= 0; i--) {
s.insert(arr[i]);
it = s.lower_bound(arr[i]);
// Condition to check if there
// is such element exists
if (it != s.begin()) {
it--;
Right[i] = *it;
}
// If no such element exists.
else {
Right[i] = -1;
}
}
int ans = -1;
// Loop to find the maximum product
// bitonic subsequence of size 3
for (int i = 0; i < n; i++) {
if (Left[i] > 0 and Right[i] > 0)
ans = max(ans, arr[i] * Left[i] * Right[i]);
}
if (ans < 0) {
return -1;
}
else {
return ans;
}
}
// Driver Code
int main()
{
int arr[] = { 1, 8, 3, 7, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << maxProduct(arr, n);
}
Java
// Java implementation to find the
// maximum product of the bitonic
// subsequence of size 3
import java.util.*;
import java.lang.System;
class GFG{
public static int maxProduct(int arr[],int n)
{
// Self Balancing BST
TreeSet<Integer> ts = new TreeSet<Integer>();
// Left array to store the
// maximum smallest value for
// every element in left of it
int Left[] = new int[n];
// Right array to store the
// maximum smallest value for
// every element in right of it
int Right[] = new int[n];
// Loop to find the maximum
// smallest element in left of
// every element in array
for(int i = 0; i < n; i++)
{
ts.add(arr[i]);
if(ts.lower(arr[i]) == null)
Left[i] = -1;
else
Left[i] = ts.lower(arr[i]);
}
ts.clear();
// Loop to find the maximum
// smallest element in right of
// every element in array
for (int i = n-1; i >= 0; i--)
{
ts.add(arr[i]);
if(ts.lower(arr[i]) == null)
Right[i] = -1;
else
Right[i] = ts.lower(arr[i]);
}
// Loop to find the maximum product
// bitonic subsequence of size 3
int ans = 0;
for(int i = 0; i < n; i++)
{
//Condition to check whether a sequence is bitonic or not
if(Left[i] != -1 && Right[i] != -1)
ans = Math.max(ans, Left[i] * arr[i] * Right[i]);
}
return ans;
}
// Driver Code
public static void main(String args[])
{
int arr[] = {1, 8, 3, 7, 5, 6, 7 };
int n = arr.length;
int maximum_product = maxProduct(arr,n);
System.out.println(maximum_product);
}
}
// This code is contributed by Siddhi.
Producción:
126
Análisis de rendimiento:
- Complejidad temporal: O(NlogN).
- Espacio Auxiliar: O(N).