Рубрики

Максимальные и минимальные подмножества продукта

Для данного набора нам нужно найти максимально и минимально возможное произведение среди всех подмножеств набора.
Примеры:

Input : arr[] = {4, -2, 5};
Output: Maximum product = 20 
        Minimum product = -40
Maximum product is obtained by multiplying
4 5
Minimum product is obtained by multiplying 
4, -2, 5

Input : arr[] = {-4, -2, 3, 7, 5, 0, 1};
Output: Maximum product = 840 
        Minimum product = -420
Maximum product is obtained by multiplying
-4, -2, 3, 7, 5
Minimum product is obtained by multiplying 
-4, 3, 7, 5

Так как массив может иметь отрицательное значение, ноль и положительное значение, эта проблема может иметь множество крайних случаев, если не атаковать должным образом. Ниже данное решение поддерживает максимальный продукт и минимальный продукт при текущем индексе и предыдущем индексе, и в любой момент текущий продукт принимает значение из предыдущего максимального или предыдущего минимума, умноженного на текущий элемент, в зависимости от знака текущего элемента. Например, если мы находим максимальный продукт, то текущий максимум будет равен предыдущему максимуму, умноженному на текущее значение, если текущий элемент положителен, в противном случае предыдущий минимум умножит текущее значение, если текущий элемент отрицателен. Та же процедура применяется для нахождения минимального продукта также.
Пожалуйста, смотрите ниже простой код, чтобы понять.

C ++

// C ++ программа для поиска максимума и минимума
// произведение из массива
#include <bits/stdc++.h>

using namespace std;

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

pair<int, int> getMaxandMinProduct(int arr[], int n)

{

    // Инициализируем все продукты с arr [0]

    int curMaxProduct = arr[0];

    int curMinProduct = arr[0];

    int prevMaxProduct = arr[0];

    int prevMinProduct = arr[0];

    int maxProduct = arr[0];

    int minProduct = arr[0];

  

    // Обработка всех элементов после arr [0]

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

    {

        / * Текущий максимальный продукт является максимальным из следующих

            1) prevMax * curelement (когда curelement + ve)

            2) prevMin * curelement (когда curelement - -ve)

            3) Сам элемент

            4) Предыдущий максимальный продукт * /

        curMaxProduct = max(prevMaxProduct * arr[i],

                            max(prevMinProduct * arr[i],

                                arr[i]));

        curMaxProduct = max(curMaxProduct, prevMaxProduct);

  

        / * Расчет текущего минимального продукта аналогичен

           что из текущего максимума profuct * /

        curMinProduct = min(prevMaxProduct * arr[i],

                            min(prevMinProduct * arr[i],

                                arr[i]));

        curMinProduct = min(curMinProduct, prevMinProduct);

        maxProduct = max(maxProduct, curMaxProduct);

        minProduct = min(minProduct, curMinProduct);

  

        // копировать текущие значения в предыдущие значения

        prevMaxProduct = curMaxProduct;

        prevMinProduct = curMinProduct;

    }

  

    return make_pair(minProduct, maxProduct);

}

  
// код драйвера для тестирования вышеуказанных методов

int main()

{

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

    int n = sizeof(arr) / sizeof(int);

    pair<int, int> product = getMaxandMinProduct(arr, n);

    printf("Minimum product is %d and "

            "Maximum product is %dn",

             product.first, product.second);

    return 0;

}

Джава

// Java программа для поиска максимума и минимума
// произведение из массива

class GFG

{

static class pair 

    int first, second; 

    public pair(int first, int second) 

    

        this.first = first; 

        this.second = second; 

    

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

static pair getMaxandMinProduct(int arr[], int n) 

    // Инициализируем все продукты с arr [0]

    int curMaxProduct = arr[0]; 

    int curMinProduct = arr[0]; 

    int prevMaxProduct = arr[0]; 

    int prevMinProduct = arr[0]; 

    int maxProduct = arr[0]; 

    int minProduct = arr[0]; 

  

    // Обработка всех элементов после arr [0]

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

    

        / * Текущий максимальный продукт является максимальным из следующих

            1) prevMax * curelement (когда curelement + ve)

            2) prevMin * curelement (когда curelement - -ve)

            3) Сам элемент

            4) Предыдущий максимальный продукт * /

        curMaxProduct = Math.max(prevMaxProduct * arr[i], 

                        Math.max(prevMinProduct * arr[i], 

                                                  arr[i])); 

        curMaxProduct = Math.max(curMaxProduct, 

                                 prevMaxProduct); 

  

        / * Текущий расчет минимального продукта

        Похоже на текущий максимальный профук * /

        curMinProduct = Math.min(prevMaxProduct * arr[i], 

                        Math.min(prevMinProduct * arr[i], 

                                                  arr[i])); 

        curMinProduct = Math.min(curMinProduct, prevMinProduct); 

        maxProduct = Math.max(maxProduct, curMaxProduct); 

        minProduct = Math.min(minProduct, curMinProduct); 

  

        // копировать текущие значения в предыдущие значения

        prevMaxProduct = curMaxProduct; 

        prevMinProduct = curMinProduct; 

    }

    return new pair(minProduct, maxProduct); 

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

public static void main(String[] args)

{

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

    int n = arr.length; 

    pair product = getMaxandMinProduct(arr, n); 

    System.out.printf("Minimum product is %d and "

                      "Maximum product is %d"

                       product.first, product.second); 

    }

}

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

python3

# Python3 программа для поиска максимума и
# минимальное произведение из массива

  
# метод возвращает максимум и минимум
# получаемый продукт массива обр

def getMaxandMinProduct(arr, n):

  

    # Инициализировать все продукты с arr [0]

    curMaxProduct = arr[0]

    curMinProduct = arr[0]

    prevMaxProduct = arr[0]

    prevMinProduct = arr[0]

    maxProduct = arr[0]

    minProduct = arr[0]

  

    # Обработка всех элементов после arr [0]

    for i in range(1, n):

  

        # Текущий максимальный продукт является максимальным из следующих

        # 1) лекарство prevMax * (когда лекарство + ve)

        # 2) prevMin * curelement (когда curelement - -ve)

        # 3) Сам элемент

        # 4) Предыдущий максимальный продукт

        curMaxProduct = max(prevMaxProduct * arr[i],

                        max(prevMinProduct * arr[i], arr[i]))

        curMaxProduct = max(curMaxProduct, prevMaxProduct)

  

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

        # это текущее максимальное значение

        curMinProduct = min(prevMaxProduct * arr[i],

                        min(prevMinProduct * arr[i], arr[i]))

        curMinProduct = min(curMinProduct, prevMinProduct)

        maxProduct = max(maxProduct, curMaxProduct)

        minProduct = min(minProduct, curMinProduct)

  

        # копировать текущие значения в предыдущие значения

        prevMaxProduct = curMaxProduct

        prevMinProduct = curMinProduct

  

    return (minProduct, maxProduct)

  
Код водителя

if __name__ == "__main__":

    arr = [-4, -2, 3, 7, 5, 0, 1]

    n = len(arr)

    product = getMaxandMinProduct(arr, n)

    print("Minimum product is", product[0], "and",

          "Maximum product is", product[1])

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

C #

// C # программа для поиска максимума и минимума
// произведение из массива

using System;

  

class GFG

{

public class pair 

    public int first, second; 

    public pair(int first, int second) 

    

        this.first = first; 

        this.second = second; 

    

  
// метод возвращает максимум и минимум
// получаемый продукт массива обр

static pair getMaxandMinProduct(int []arr, 

                                int n) 

    // Инициализируем все продукты с arr [0]

    int curMaxProduct = arr[0]; 

    int curMinProduct = arr[0]; 

    int prevMaxProduct = arr[0]; 

    int prevMinProduct = arr[0]; 

    int maxProduct = arr[0]; 

    int minProduct = arr[0]; 

  

    // Обработка всех элементов после arr [0]

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

    

        / * Текущий максимальный продукт является максимальным из следующих

            1) prevMax * curelement (когда curelement + ve)

            2) prevMin * curelement (когда curelement - -ve)

            3) Сам элемент

            4) Предыдущий максимальный продукт * /

        curMaxProduct = Math.Max(prevMaxProduct * arr[i], 

                        Math.Max(prevMinProduct * arr[i], 

                                                  arr[i])); 

        curMaxProduct = Math.Max(curMaxProduct, 

                                 prevMaxProduct); 

  

        / * Текущий расчет минимального продукта

        Похоже на текущий максимальный профук * /

        curMinProduct = Math.Min(prevMaxProduct * arr[i], 

                        Math.Min(prevMinProduct * arr[i], 

                                                  arr[i])); 

        curMinProduct = Math.Min(curMinProduct, 

                                 prevMinProduct); 

        maxProduct = Math.Max(maxProduct, curMaxProduct); 

        minProduct = Math.Min(minProduct, curMinProduct); 

  

        // копировать текущие значения в предыдущие значения

        prevMaxProduct = curMaxProduct; 

        prevMinProduct = curMinProduct; 

    }

    return new pair(minProduct, maxProduct); 

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

public static void Main(String[] args)

{

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

    int n = arr.Length; 

    pair product = getMaxandMinProduct(arr, n); 

    Console.Write("Minimum product is {0} and "

                  "Maximum product is {1}"

                   product.first, product.second); 

}
}

  
// Этот код предоставлен Принчи Сингхом



Выход:

Minimum product is -420 and Maximum product is 840

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Максимальные и минимальные подмножества продукта

0.00 (0%) 0 votes