Рубрики

Максимальное произведение триплета (последующее значение размера 3) в массиве

По заданному целочисленному массиву найдите максимальное произведение триплета в массиве.

Примеры:

Input:  [10, 3, 5, 6, 20]
Output: 1200
Multiplication of 10, 6 and 20
 
Input:  [-10, -3, -5, -6, -20]
Output: -90

Input:  [1, -4, 3, -6, 7, 0]
Output: 168

Подход 1 (Наивный, O (n 3 ) время, O (1) Пространство)
Простое решение — проверить каждый триплет, используя три вложенных цикла. Ниже его реализация —

C ++

// Программа на C ++ для поиска максимального продукта
// триплет в массиве целых чисел
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция найти максимальное произведение триплета

   в массиве целых чисел размера n * /

int maxProduct(int arr[], int n)

{

    // если размер меньше 3, триплет не существует

    if (n < 3)

        return -1;

  

    // будет содержать максимальный продукт

    int max_product = INT_MIN;

  

    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++)

                max_product = max(max_product,

                        arr[i] * arr[j] * arr[k]);

  

    return max_product;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr[] = { 10, 3, 5, 6, 20 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    int max = maxProduct(arr, n);

  

    if (max == -1)

        cout << "No Triplet Exists";

    else

        cout << "Maximum product is " << max;

  

    return 0;

}

Джава

// Java-программа для поиска
// максимальный продукт
// триплет в массиве целых чисел

  

class GFG {

       
// Функция для поиска максимума
// произведение триплета в массиве
// целых чисел размера n

static int maxProduct(int []arr, int n)

{

       

    // если размер меньше чем

    // 3, триплета не существует

    if (n < 3)

        return -1;

   

    // будет содержать максимальный продукт

    int max_product = Integer.MIN_VALUE;

   

    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++)

                max_product = Math.max(max_product,

                          arr[i] * arr[j] * arr[k]);

   

    return max_product;

}

   

    // Код драйвера

    public static void main (String [] args)

    {

        int []arr = { 10, 3, 5, 6, 20 };

        int n = arr.length;;

   

        int max = maxProduct(arr, n);

   

        if (max == -1)

            System.out.println("No Triplet Exists");

        else

            System.out.println("Maximum product is " + max);

    }

}

  

python3

# Python программа для поиска максимума
# произведение триплета в массиве
число целых чисел

import sys

  
# Функция поиска максимума
# произведение триплета в массиве
число целых чисел размера n

def maxProduct(arr, n):

  

    # если размер меньше 3,

    # триплет не существует

    if n < 3:

        return -1

  

    # будет содержать максимальный продукт

    max_product = -(sys.maxsize - 1)

      

    for i in range(0, n - 2):

        for j in range(i + 1, n - 1):

            for k in range(j + 1, n):

                max_product = max(

                    max_product, arr[i]

                    * arr[j] * arr[k])

  

    return max_product

  
# Драйверная программа

arr = [10, 3, 5, 6, 20]

n = len(arr)

  

max = maxProduct(arr, n)

  

if max == -1:

    print("No Tripplet Exits")

else:

    print("Maximum product is", max)

  
# Этот код предоставлен Shrikant13

C #

// AC # программа для поиска
// максимальный продукт
// триплет в массиве целых чисел

using System;

class GFG {

      
// Функция для поиска максимума
// произведение триплета в массиве
// целых чисел размера n

static int maxProduct(int []arr, int n)

{

      

    // если размер меньше чем

    // 3, триплета не существует

    if (n < 3)

        return -1;

  

    // будет содержать максимальный продукт

    int max_product = int.MinValue;

  

    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++)

                max_product = Math.Max(max_product,

                          arr[i] * arr[j] * arr[k]);

  

    return max_product;

}

  

    // Код драйвера

    public static void Main ()

    {

        int []arr = { 10, 3, 5, 6, 20 };

        int n = arr.Length;;

  

        int max = maxProduct(arr, n);

  

        if (max == -1)

            Console.WriteLine("No Triplet Exists");

        else

            Console.WriteLine("Maximum product is " + max);

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP программа для поиска
// максимальный продукт
// триплет в массиве целых чисел

  
// Функция для поиска максимума
// произведение триплета
// в массиве целых чисел
// размер n

function maxProduct($arr, $n)

{

    $INT_MIN = 0;

      

    // если размер меньше чем

    // 3, триплета не существует

    if ($n < 3)

        return -1;

  

    // будет содержать максимальный продукт

    $max_product = $INT_MIN;

  

    for ($i = 0; $i < $n - 2; $i++)

        for ($j = $i + 1; $j < $n - 1; $j++)

            for ($k = $j + 1; $k < $n; $k++)

                $max_product = max($max_product,

                        $arr[$i] * $arr[$j] * $arr[$k]);

  

    return $max_product;

}

  

    // Код драйвера

    $arr = array(10, 3, 5, 6, 20 );

    $n = sizeof($arr);

    $max = maxProduct($arr, $n);

    if ($max == -1)

        echo "No Triplet Exists";

    else

        echo "Maximum product is " ,$max;

  
// Этот код предоставлен нитин митталь.
?>


Выход :

Maximum product is 1200

Подход 2: O (n) Время, O (n) Пространство

  1. Создайте четыре вспомогательных массива leftMax [], rightMax [], leftMin [] и rightMin [] того же размера, что и входной массив.
  2. Заполните leftMax [], rightMax [], leftMin [] и rightMin [] следующим образом.
    • leftMax [i] будет содержать максимальный элемент слева от arr [i], исключая arr [i]. Для индекса 0 слева будет содержаться -1.
    • leftMin [i] будет содержать минимальный элемент слева от arr [i], исключая arr [i]. Для индекса 0 слева будет содержаться -1.
    • rightMax [i] будет содержать максимальный элемент справа от arr [i], исключая arr [i]. Для индекса n-1 право будет содержать -1.
    • rightMin [i] будет содержать минимальный элемент справа от arr [i], исключая arr [i]. Для индекса n-1 право будет содержать -1.
  3. Для всех индексов массива i, кроме первого и последнего индекса, вычислите максимум arr [i] * x * y, где x может быть leftMax [i] или leftMin [i], а y может быть rightMax [i] или rightMin [i].
  4. Верните максимум с шага 3.

Ниже его реализация —

C ++

// Программа на C ++ для поиска максимального произведения триплета
// в массиве целых чисел
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция найти максимальное произведение триплета
в массиве целых чисел размера n * /

int maxProduct(int arr[], int n)

{

    // если размер меньше 3, триплет не существует

    if (n < 3)

        return -1;

  

    // Построить четыре вспомогательных вектора

    // размера n и инициализировать их -1

    vector<int> leftMin(n, -1);

    vector<int> rightMin(n, -1);

    vector<int> leftMax(n, -1);

    vector<int> rightMax(n, -1);

  

    // будет содержать максимальный продукт

    int max_product = INT_MIN;

  

    // сохранить максимальный элемент слева от массива

    int max_sum = arr[0];

  

    // сохранить минимальный элемент слева от массива

    int min_sum = arr[0];

  

    // leftMax [i] будет содержать элемент max

    // слева от arr [i], исключая arr [i].

    // leftMin [i] будет содержать элемент min

    // слева от arr [i], исключая arr [i].

    for (int i = 1; i < n; i++)

    {

        leftMax[i] = max_sum;

        if (arr[i] > max_sum)

            max_sum = arr[i];

  

        leftMin[i] = min_sum;

        if (arr[i] < min_sum)

            min_sum = arr[i];

    }

  

    // сбрасываем max_sum для сохранения максимального элемента

    // справа от массива

    max_sum = arr[n - 1];

  

    // сбрасываем min_sum для сохранения минимального элемента

    // справа от массива

    min_sum = arr[n - 1];

  

    // rightMax [i] будет содержать элемент max

    // справа от arr [i], исключая arr [i].

    // rightMin [i] будет содержать элемент min

    // справа от arr [i], исключая arr [i].

    for (int j = n - 2; j >= 0; j--)

    {

        rightMax[j] = max_sum;

        if (arr[j] > max_sum)

            max_sum = arr[j];

  

        rightMin[j] = min_sum;

        if (arr[j] < min_sum)

            min_sum = arr[j];

    }

  

    // Для всех индексов массива i, кроме first и

    // последний, вычисляем максимум arr [i] * x * y, где

    // x может быть leftMax [i] или leftMin [i] и

    // у может быть rightMax [i] или rightMin [i].

    for (int i = 1; i < n - 1; i++)

    {

        int max1 = max(arr[i] * leftMax[i] * rightMax[i],

                    arr[i] * leftMin[i] * rightMin[i]);

  

        int max2 = max(arr[i] * leftMax[i] * rightMin[i],

                    arr[i] * leftMin[i] * rightMax[i]);

  

        max_product = max(max_product, max(max1, max2));

    }

  

    return max_product;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr[] = { 1, 4, 3, -6, -7, 0 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    int max = maxProduct(arr, n);

  

    if (max == -1)

        cout << "No Triplet Exists";

    else

        cout << "Maximum product is " << max;

  

    return 0;

}

Джава

// Java-программа для поиска максимального произведения триплета
// в массиве целых чисел

import java.util.*;

  

class GFG

{

      
/ * Функция найти максимальное произведение триплета
в массиве целых чисел размера n * /

static int maxProduct(int []arr, int n)

{

    // если размер меньше 3, триплет не существует

    if (n < 3)

        return -1;

  

    // Построить четыре вспомогательных вектора

    // размера n и инициализировать их -1

    int[] leftMin = new int[n];

    int[] rightMin = new int[n];

    int[] leftMax = new int[n];

    int[] rightMax = new int[n];

    Arrays.fill(leftMin, -1);

    Arrays.fill(leftMax, -1);

    Arrays.fill(rightMax, -1);

    Arrays.fill(rightMin, -1);

  

    // будет содержать максимальный продукт

    int max_product = Integer.MIN_VALUE;

  

    // сохранить максимальный элемент слева от массива

    int max_sum = arr[0];

  

    // сохранить минимальный элемент слева от массива

    int min_sum = arr[0];

  

    // leftMax [i] будет содержать элемент max

    // слева от arr [i], исключая arr [i].

    // leftMin [i] будет содержать элемент min

    // слева от arr [i], исключая arr [i].

    for (int i = 1; i < n; i++)

    {

        leftMax[i] = max_sum;

        if (arr[i] > max_sum)

            max_sum = arr[i];

  

        leftMin[i] = min_sum;

        if (arr[i] < min_sum)

            min_sum = arr[i];

    }

  

    // сбрасываем max_sum для сохранения максимального элемента

    // справа от массива

    max_sum = arr[n - 1];

  

    // сбрасываем min_sum для сохранения минимального элемента

    // справа от массива

    min_sum = arr[n - 1];

  

    // rightMax [i] будет содержать элемент max

    // справа от arr [i], исключая arr [i].

    // rightMin [i] будет содержать элемент min

    // справа от arr [i], исключая arr [i].

    for (int j = n - 2; j >= 0; j--)

    {

        rightMax[j] = max_sum;

        if (arr[j] > max_sum)

            max_sum = arr[j];

  

        rightMin[j] = min_sum;

        if (arr[j] < min_sum)

            min_sum = arr[j];

    }

  

    // Для всех индексов массива i, кроме first и

    // последний, вычисляем максимум arr [i] * x * y, где

    // x может быть leftMax [i] или leftMin [i] и

    // у может быть rightMax [i] или rightMin [i].

    for (int i = 1; i < n - 1; i++)

    {

        int max1 = Math.max(arr[i] * leftMax[i] * rightMax[i],

                    arr[i] * leftMin[i] * rightMin[i]);

  

        int max2 = Math.max(arr[i] * leftMax[i] * rightMin[i],

                    arr[i] * leftMin[i] * rightMax[i]);

  

        max_product = Math.max(max_product, Math.max(max1, max2));

    }

  

    return max_product;

}

  
// Код драйвера

public static void main (String[] args) 

{

    int []arr = { 1, 4, 3, -6, -7, 0 };

    int n = arr.length;

  

    int max = maxProduct(arr, n);

  

    if (max == -1)

        System.out.println("No Triplet Exists");

    else

        System.out.println("Maximum product is "+max);

}
}

  
// Этот код предоставлен mits

C #

// AC # программа для поиска максимального произведения триплета
// в массиве целых чисел

using System;

  

class GFG

{

      
/ * Функция найти максимальное произведение триплета
в массиве целых чисел размера n * /

static int maxProduct(int []arr, int n)

{

    // если размер меньше 3, триплет не существует

    if (n < 3)

        return -1;

  

    // Построить четыре вспомогательных вектора

    // размера n и инициализировать их -1

    int[] leftMin=new int[n];

    int[] rightMin=new int[n];

    int[] leftMax=new int[n];

    int[] rightMax=new int[n];

    Array.Fill(leftMin,-1);

    Array.Fill(leftMax,-1);

    Array.Fill(rightMax,-1);

    Array.Fill(rightMin,-1);

  

    // будет содержать максимальный продукт

    int max_product = int.MinValue;

  

    // сохранить максимальный элемент слева от массива

    int max_sum = arr[0];

  

    // сохранить минимальный элемент слева от массива

    int min_sum = arr[0];

  

    // leftMax [i] будет содержать элемент max

    // слева от arr [i], исключая arr [i].

    // leftMin [i] будет содержать элемент min

    // слева от arr [i], исключая arr [i].

    for (int i = 1; i < n; i++)

    {

        leftMax[i] = max_sum;

        if (arr[i] > max_sum)

            max_sum = arr[i];

  

        leftMin[i] = min_sum;

        if (arr[i] < min_sum)

            min_sum = arr[i];

    }

  

    // сбрасываем max_sum для сохранения максимального элемента

    // справа от массива

    max_sum = arr[n - 1];

  

    // сбрасываем min_sum для сохранения минимального элемента

    // справа от массива

    min_sum = arr[n - 1];

  

    // rightMax [i] будет содержать элемент max

    // справа от arr [i], исключая arr [i].

    // rightMin [i] будет содержать элемент min

    // справа от arr [i], исключая arr [i].

    for (int j = n - 2; j >= 0; j--)

    {

        rightMax[j] = max_sum;

        if (arr[j] > max_sum)

            max_sum = arr[j];

  

        rightMin[j] = min_sum;

        if (arr[j] < min_sum)

            min_sum = arr[j];

    }

  

    // Для всех индексов массива i, кроме first и

    // последний, вычисляем максимум arr [i] * x * y, где

    // x может быть leftMax [i] или leftMin [i] и

    // у может быть rightMax [i] или rightMin [i].

    for (int i = 1; i < n - 1; i++)

    {

        int max1 = Math.Max(arr[i] * leftMax[i] * rightMax[i],

                    arr[i] * leftMin[i] * rightMin[i]);

  

        int max2 = Math.Max(arr[i] * leftMax[i] * rightMin[i],

                    arr[i] * leftMin[i] * rightMax[i]);

  

        max_product = Math.Max(max_product, Math.Max(max1, max2));

    }

  

    return max_product;

}

  
// Код драйвера

static void Main()

{

    int []arr = { 1, 4, 3, -6, -7, 0 };

    int n = arr.Length;

  

    int max = maxProduct(arr, n);

  

    if (max == -1)

        Console.WriteLine("No Triplet Exists");

    else

        Console.WriteLine("Maximum product is "+max);

  
}
}

  
// Этот код предоставлен mits

PHP

<?php
// PHP-программа для поиска максимального произведения триплета
// в массиве целых чисел

  
/ * Функция найти максимальное произведение триплета
в массиве целых чисел размера n * /

function maxProduct($arr, $n)

{

    // если размер меньше 3, триплет не существует

    if ($n < 3)

        return -1;

  

    // Построить четыре вспомогательных вектора

    // размера n и инициализировать их -1

    $leftMin=array_fill(0,$n, -1);

    $rightMin=array_fill(0,$n, -1);

    $leftMax=array_fill(0,$n, -1);

    $rightMax=array_fill(0,$n, -1);

  

    // будет содержать максимальный продукт

    $max_product = PHP_INT_MIN;

  

    // сохранить максимальный элемент слева от массива

    $max_sum = $arr[0];

  

    // сохранить минимальный элемент слева от массива

    $min_sum = $arr[0];

  

    // leftMax [i] будет содержать элемент max

    // слева от arr [i], исключая arr [i].

    // leftMin [i] будет содержать элемент min

    // слева от arr [i], исключая arr [i].

    for ($i = 1; $i < $n; $i++)

    {

        $leftMax[$i] = $max_sum;

        if ($arr[$i] > $max_sum)

            $max_sum = $arr[$i];

  

        $leftMin[$i] = $min_sum;

        if ($arr[$i] < $min_sum)

            $min_sum = $arr[$i];

    }

  

    // сбрасываем max_sum для сохранения максимального элемента

    // справа от массива

    $max_sum = $arr[$n - 1];

  

    // сбрасываем min_sum для сохранения минимального элемента

    // справа от массива

    $min_sum = $arr[$n - 1];

  

    // rightMax [i] будет содержать элемент max

    // справа от arr [i], исключая arr [i].

    // rightMin [i] будет содержать элемент min

    // справа от arr [i], исключая arr [i].

    for ($j = $n - 2; $j >= 0; $j--)

    {

        $rightMax[$j] = $max_sum;

        if ($arr[$j] > $max_sum)

            $max_sum = $arr[$j];

  

        $rightMin[$j] = $min_sum;

        if ($arr[$j] < $min_sum)

            $min_sum = $arr[$j];

    }

  

    // Для всех индексов массива i, кроме first и

    // последний, вычисляем максимум arr [i] * x * y, где

    // x может быть leftMax [i] или leftMin [i] и

    // у может быть rightMax [i] или rightMin [i].

    for ($i = 1; $i < $n - 1; $i++)

    {

        $max1 = max($arr[$i] * $leftMax[$i] * $rightMax[$i],

                    $arr[$i] * $leftMin[$i] * $rightMin[$i]);

  

        $max2 = max($arr[$i] * $leftMax[$i] * $rightMin[$i],

                    $arr[$i] * $leftMin[$i] * $rightMax[$i]);

  

        $max_product = max($max_product, max($max1, $max2));

    }

  

    return $max_product;

}

  
// Программа драйвера для проверки вышеуказанных функций

    $arr = array( 1, 4, 3, -6, -7, 0 );

    $n = count($arr);

  

    $max = maxProduct($arr, $n);

  

    if ($max == -1)

        echo "No Triplet Exists";

    else

        echo "Maximum product is ".$max;

  

  
// Этот код предоставлен mits
?>


Выход :

Maximum product is 168

Подход 3: O (nlogn) Время, O (1) Пространство

  1. Сортируйте массив, используя эффективный алгоритм сортировки по месту в порядке возрастания.
  2. Вернуть максимум произведения трех последних элементов массива и произведения первых двух элементов и последнего элемента.
    1. Ниже приведена реализация вышеуказанного подхода —
      C ++

      // Программа на C ++ для поиска максимального продукта
      // триплет в массиве целых чисел
      #include <bits/stdc++.h>

      using namespace std;

        
      / * Функция найти максимальное произведение триплета

         в массиве целых чисел размера n * /

      int maxProduct(int arr[], int n)

      {

          // если размер меньше 3, триплет не существует

          if (n < 3)

              return -1;

        

          // Сортировка массива в порядке возрастания

          sort(arr, arr + n);

        

          // Возвращаем максимум продукта из последних трех

          // элементы и произведение первых двух элементов

          // и последний элемент

          return max(arr[0] * arr[1] * arr[n - 1],

                     arr[n - 1] * arr[n - 2] * arr[n - 3]);

      }

        
      // Программа драйвера для проверки вышеуказанных функций

      int main()

      {

          int arr[] = { -10, -3, 5, 6, -20 };

          int n = sizeof(arr) / sizeof(arr[0]);

        

          int max = maxProduct(arr, n);

        

          if (max == -1)

              cout << "No Triplet Exists";

          else

              cout << "Maximum product is " << max;

        

          return 0;

      }

      Джава

      // Java-программа для поиска максимального продукта
      // триплет в массиве целых чисел

        

      import java.util.Arrays;

        

      class GFG {

        

          / * Функция найти максимальное произведение триплета

         в массиве целых чисел размера n * /

          static int maxProduct(int arr[], int n) {

              // если размер меньше 3, триплет не существует

              if (n < 3) {

                  return -1;

              }

        

              // Сортировка массива в порядке возрастания

              Arrays.sort(arr);

        

              // Возвращаем максимум продукта из последних трех

              // элементы и произведение первых двух элементов

              // и последний элемент

              return Math.max(arr[0] * arr[1] * arr[n - 1],

                      arr[n - 1] * arr[n - 2] * arr[n - 3]);

          }

        
      // Программа драйвера для проверки вышеуказанных функций

          public static void main(String[] args) {

              int arr[] = {-10, -3, 5, 6, -20};

              int n = arr.length;

        

              int max = maxProduct(arr, n);

        

              if (max == -1) {

                  System.out.println("No Triplet Exists");

              } else {

                  System.out.println("Maximum product is " + max);

              }

        

          }

      }
      / * Этот Java-код предоставлен Rajput-Ji * /

      python3

      # Программа Python3, чтобы найти максимум
      # произведение триплета в массиве целых чисел

        
      # Функция, чтобы найти максимальный продукт
      # триплет в массиве целых чисел размера n

      def maxProduct(arr, n): 

        

          # если размер меньше 3, триплет не существует

          if n < 3:

              return -1

        

          # Сортировать массив в порядке возрастания

          arr.sort()

        

          # Вернуть максимум продукта последнего

          # три элемента и произведение первого

          # два элемента и последний элемент

          return max(arr[0] * arr[1] * arr[n - 1], 

                     arr[n - 1] * arr[n - 2] * arr[n - 3]) 

        
      Код водителя

      if __name__ == "__main__":

        

          arr = [-10, -3, 5, 6, -20

          n = len(arr) 

        

          _max = maxProduct(arr, n) 

        

          if _max == -1

              print("No Triplet Exists"

          else:

              print("Maximum product is", _max) 

        
      # Этот код предоставлен Rituraj Jain

      C #

      // C # программа для поиска максимального продукта
      // триплет в массиве целых чисел

      using System;

      public class GFG { 

        

          / * Функция найти максимальное произведение триплета

      в массиве целых чисел размера n * /

          static int maxProduct(int []arr, int n) { 

              // если размер меньше 3, триплет не существует

              if (n < 3) { 

                  return -1; 

              

        

              // Сортировка массива в порядке возрастания

              Array.Sort(arr); 

        

              // Возвращаем максимум продукта из последних трех

              // элементы и произведение первых двух элементов

              // и последний элемент

              return Math.Max(arr[0] * arr[1] * arr[n - 1], 

                      arr[n - 1] * arr[n - 2] * arr[n - 3]); 

          

        
      // Программа драйвера для проверки вышеуказанных функций

          public static void Main() { 

              int []arr = {-10, -3, 5, 6, -20}; 

              int n = arr.Length; 

        

              int max = maxProduct(arr, n); 

        

              if (max == -1) { 

                  Console.WriteLine("No Triplet Exists"); 

              } else

                  Console.WriteLine("Maximum product is " + max); 

              

        

          


      // Этот код предоставлен 29AjayKumar

      PHP

      <?php
      // PHP-программа для поиска максимального продукта
      // триплет в массиве целых чисел

        
      / * Функция найти максимальное произведение триплета
      в массиве целых чисел размера n * /

          function maxProduct($arr, $n

            

          // если размер меньше 3, триплет не существует

          

              if ($n < 3) 

              {

                  return -1;

              }

        

              // Сортировка массива в порядке возрастания

              sort($arr);

        

              // Возвращаем максимум продукта из последних трех

              // элементы и произведение первых двух элементов

              // и последний элемент

              return max($arr[0] * $arr[1] * $arr[$n - 1],

                      $arr[$n - 1] * $arr[$n - 2] * $arr[$n - 3]);

          }

        

          // Код драйвера

          $arr = array(-10, -3, 5, 6, -20);

          $n = sizeof($arr);

        

          $max = maxProduct($arr, $n);

        

          if ($max == -1)

          {

              echo("No Triplet Exists");

          

          else

          {

              echo("Maximum product is " . $max);

          }

        

        
      / * Этот код предоставлен Code_Mech * /


      Выход :

      Maximum product is 1200

      Подход 4: O (n) Время, O (1) Пространство

      1. Сканирование массива и вычисление максимального, второго максимального и третьего максимального элемента, присутствующего в массиве.
      2. Сканирование массива и вычисление минимального и второго минимального элемента, присутствующего в массиве.
      3. Возвращает максимум произведения Максимум, второй максимум и третий максимум, а также произведение Минимума, второго минимума и элемента Максимум.

      Примечание. Шаг 1 и шаг 2 можно выполнить за один проход массива.

      Ниже его реализация C ++ —

      // AO (n) C ++ программа для поиска максимальной пары продуктов в
      // массив.
      #include <bits/stdc++.h>

      using namespace std;

        
      / * Функция найти максимальное произведение триплета

         в массиве целых чисел размера n * /

      int maxProduct(int arr[], int n)

      {

          // если размер меньше 3, триплет не существует

          if (n < 3)

              return -1;

        

          // Инициализируем максимум, второй максимум и третий

          // максимальный элемент

          int maxA = INT_MIN, maxB = INT_MIN, maxC = INT_MIN;

        

          // Инициализируем минимальный и второй минимальный элемент

          int minA = INT_MAX, minB = INT_MAX;

        

          for (int i = 0; i < n; i++)

          {

              // Обновить максимум, второй максимум и третий

              // максимальный элемент

              if (arr[i] > maxA)

              {

                  maxC = maxB;

                  maxB = maxA;

                  maxA = arr[i];

              }

        

              // Обновляем второй максимум и третий максимальный элемент

              else if (arr[i] > maxB)

              {

                  maxC = maxB;

                  maxB = arr[i];

              }

        

              // Обновляем третий максимальный элемент

              else if (arr[i] > maxC)

                  maxC = arr[i];

        

              // Обновить минимальный и второй минимальный элемент

              if (arr[i] < minA)

              {

                  minB = minA;

                  minA = arr[i];

              }

        

              // Обновляем второй элемент минимума

              else if(arr[i] < minB)

                  minB = arr[i];

          }

        

          return max(minA * minB * maxA,

                     maxA * maxB * maxC);

      }

        
      // Программа драйвера для проверки вышеуказанной функции

      int main()

      {

          int arr[] = { 1, -4, 3, -6, 7, 0 };

          int n = sizeof(arr) / sizeof(arr[0]);

        

          int max = maxProduct(arr, n);

        

          if (max == -1)

              cout << "No Triplet Exists";

          else

              cout << "Maximum product is " << max;

        

          return 0;

      }

      Выход :

      Maximum product is 168

      Упражнение:
      1. Распечатайте триплет с максимальным продуктом.

      2. Найдите минимальное произведение триплета в массиве.

      Эта статья предоставлена Aditya Goel . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

      Рекомендуемые посты:

      Максимальное произведение триплета (последующее значение размера 3) в массиве

      0.00 (0%) 0 votes