Максимальное произведение битонической подпоследовательности размера 3

Опубликовано: 7 Января, 2022

Для массива arr [] положительных целых чисел размера N задача состоит в том, чтобы найти максимальное произведение битонической подпоследовательности размера 3.
Bitonic Subsequence: подпоследовательность, в которой элементы сначала идут в порядке возрастания, а затем убывания. Элементы в подпоследовательности следуют в этом порядке arr [i] <arr [j]> arr [k] для i <j <k, где i, j, k - это индекс данного массива.
Примечание. Если такой элемент не найден, выведите -1.

Примеры:

Input: arr[] = {1, 8, 3, 7, 5, 6, 7} 
Output: 126 
Explanation: 
Bitonic subsequences of size 3 are 
{1, 8, 3}, {1, 8, 7}, {1, 8, 5}, {1, 8, 6}, {1, 7, 6}, {3, 7, 6}, {1, 7, 5}, {3, 7, 5}. 
Hence the maximum product of bitonic subsequence is 3*7*6 = 126

Input: arr[] = {1, 8, 3, 7} 
Output: 56 
Explanation: 
Bitonic subsequences of size 3 are 
{1, 8, 3}, {1, 8, 7}, {1, 7, 3}. 
Hence the maximum product of bitonic subsequence is 1*8*7 = 56 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: простое решение - найти произведение всех битонных подпоследовательностей размера 3 и взять из них максимум.

Алгоритм:

  • Инициализируйте ans равным -1, так что если такой подпоследовательности нет, то на выходе будет -1.
  • Выполните итерацию по массиву с тремя вложенными циклами с переменными цикла, такими как i, j и k, для выбора трех элементов массива.
  • Проверьте, есть ли arr [j]> arr [i] и arr [j]> arr [k], затем обновите ans с максимальным значением между ans и arr [i] * arr [j] * arr [k] .

Below is the implementation of the above approach: 

C++

// C++ implemenation 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 implemenation 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) +" ");   
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implemenation 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# implemenation 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  scriptimplemenation 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>
Output: 
56

 

Анализ производительности:

  • Сложность времени: Как и в вышеупомянутом подходе, существует три вложенных цикла для нахождения максимального произведения битонической подпоследовательности размера 3, следовательно, сложность времени будет O (N 3 ) .
  • Вспомогательное пространство: Как и в вышеупомянутом подходе, дополнительное пространство не используется, поэтому вспомогательное пространство будет O (1) .

Эффективный подход: идея состоит в том, чтобы найти наибольшее значение слева и справа от каждого индекса, которое меньше, чем элемент, присутствующий в текущем индексе, для этого используйте самобалансирующийся BST, а затем для каждого элемента найдите максимальный продукт которые можно сформировать и извлечь из этих продуктов максимум.
Самобалансирующийся BST реализован как установленный в C ++ и TreeSet в Java.

Алгоритм:

  • Объявите самобалансирующийся BST (скажем s ).
  • Объявите два новых массива left [] и right [], чтобы сохранить нижнюю границу для arr [i] слева от этого элемента в left [i] и нижнюю границу arr [i] справа от этого элемента в right [i].
  • Выполните цикл от 0 до length - 1, чтобы найти нижнюю границу arr [i] слева от этого элемента и сохранить ее в left [i].
  • Запустите цикл от длины -1 до 0, чтобы найти нижнюю границу arr [i] справа от этого элемента и сохранить ее в right [i].
  • Запустите цикл от 0 до длины - 1, чтобы найти битноническую подпоследовательность, которая может быть сформирована с использованием этого элемента для получения максимального произведения с использованием массива left [] и right []. То есть для каждого элемента максимальное произведение битонической подпоследовательности, которое может быть сформировано, равно left [i] * right [i] * arr [i] .

Below is the implementation of the above approach:  

C++

// C++ implemenation 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 implemenation 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]);
 
Олимпиады по программированию Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Настройка Sublime Text для соревновательного программирования (C++) с использованием плагина Fast Olympic Coding
8 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022