Étant donné un tableau contenant à la fois des entiers positifs et négatifs, trouvez le produit du sous-tableau de produits maximum. La complexité temporelle attendue est O(n) et seul l’espace supplémentaire O(1) peut être utilisé.
Exemples :
Input: arr[] = {6 -3 -10 0 2} Output: 180 // The subarray is {6 -3 -10} Input: arr[] = {-1 -3 -10 0 60} Output: 60 // The subarray is {60} Input: arr[] = {-1 -2 -3 4} Output: 24 // The subarray is {-2 -3 4} Input: arr[] = {-10} Output: 0 // An empty array is also subarray // and product of empty subarray is // considered as 0. Nous avons discuté d'une solution à ce problème ici .
Dans cet article, une solution intéressante est discutée. L'idée est basée sur le fait que le produit maximum global est au maximum de deux :
- Produit maximum en parcours de gauche à droite.
- Produit maximum en parcours de droite à gauche
Par exemple, considérons le troisième exemple d'entrée ci-dessus {-1 -2 -3 4}. Si nous parcourons le tableau uniquement vers l'avant (en considérant -1 comme faisant partie de la sortie), le produit maximum sera de 2. Si nous parcourons le tableau vers l'arrière (en considérant 4 comme faisant partie de la sortie), le produit maximum sera de 24, c'est-à-dire ; { -2 -3 4}.
Une chose importante est de gérer les 0. Nous devons calculer une nouvelle somme avant (ou arrière) chaque fois que nous voyons 0.
Vous trouverez ci-dessous la mise en œuvre de l'idée ci-dessus :
C++
// C++ program to find maximum product subarray #include
// Java program to find // maximum product subarray import java.io.*; class GFG { // Function for maximum product static int max_product(int arr[] int n) { // Initialize maximum products in // forward and backward directions int max_fwd = Integer.MIN_VALUE max_bkd = Integer.MIN_VALUE; //check if zero is present in an array or not boolean isZero=false; // Initialize current product int max_till_now = 1; // max_fwd for maximum contiguous // product in forward direction // max_bkd for maximum contiguous // product in backward direction // iterating within forward // direction in array for (int i = 0; i < n; i++) { // if arr[i]==0 it is breaking // condition for contiguous subarray max_till_now = max_till_now * arr[i]; if (max_till_now == 0) { isZero=true; max_till_now = 1; continue; } // update max_fwd if (max_fwd < max_till_now) max_fwd = max_till_now; } max_till_now = 1; // iterating within backward // direction in array for (int i = n - 1; i >= 0; i--) { max_till_now = max_till_now * arr[i]; if (max_till_now == 0) { isZero=true; max_till_now = 1; continue; } // update max_bkd if (max_bkd < max_till_now) max_bkd = max_till_now; } // return max of max_fwd and max_bkd int res = Math. max(max_fwd max_bkd); // Product should not be negative. // (Product of an empty subarray is // considered as 0) if(isZero) return Math.max(res 0); return res; } // Driver Code public static void main (String[] args) { int arr[] = {-1 -2 -3 4}; int n = arr.length; System.out.println( max_product(arr n) ); } } // This code is contributed by anuj_67.
# Python3 program to find # maximum product subarray import sys # Function for maximum product def max_product(arr n): # Initialize maximum products # in forward and backward directions max_fwd = -sys.maxsize - 1 max_bkd = -sys.maxsize - 1 #check if zero is present in an array or not isZero=False; # Initialize current product max_till_now = 1 # max_fwd for maximum contiguous # product in forward direction # max_bkd for maximum contiguous # product in backward direction # iterating within forward # direction in array for i in range(n): # if arr[i]==0 it is breaking # condition for contiguous subarray max_till_now = max_till_now * arr[i] if (max_till_now == 0): isZero=True max_till_now = 1; continue if (max_fwd < max_till_now): #update max_fwd max_fwd = max_till_now max_till_now = 1 # iterating within backward # direction in array for i in range(n - 1 -1 -1): max_till_now = max_till_now * arr[i] if (max_till_now == 0): isZero=True max_till_now = 1 continue # update max_bkd if (max_bkd < max_till_now) : max_bkd = max_till_now # return max of max_fwd and max_bkd res = max(max_fwd max_bkd) # Product should not be negative. # (Product of an empty subarray is # considered as 0) if isZero==True : return max(res 0) return res # Driver Code arr = [-1 -2 -3 4] n = len(arr) print(max_product(arr n)) # This code is contributed # by Yatin Gupta
// C# program to find maximum product // subarray using System; class GFG { // Function for maximum product static int max_product(int []arr int n) { // Initialize maximum products in // forward and backward directions int max_fwd = int.MinValue max_bkd = int.MinValue; // Initialize current product int max_till_now = 1; // max_fwd for maximum contiguous // product in forward direction // max_bkd for maximum contiguous // product in backward direction // iterating within forward // direction in array for (int i = 0; i < n; i++) { // if arr[i]==0 it is breaking // condition for contiguous subarray max_till_now = max_till_now * arr[i]; if (max_till_now == 0) { max_till_now = 1; continue; } // update max_fwd if (max_fwd < max_till_now) max_fwd = max_till_now; } max_till_now = 1; // iterating within backward // direction in array for (int i = n - 1; i >= 0; i--) { max_till_now = max_till_now * arr[i]; if (max_till_now == 0) { max_till_now = 1; continue; } // update max_bkd if (max_bkd < max_till_now) max_bkd = max_till_now; } // return max of max_fwd and max_bkd int res = Math. Max(max_fwd max_bkd); // Product should not be negative. // (Product of an empty subarray is // considered as 0) return Math.Max(res 0); } // Driver Code public static void Main () { int []arr = {-1 -2 -3 4}; int n = arr.Length; Console.Write( max_product(arr n) ); } } // This code is contributed by nitin mittal.
// PHP program to find maximum // product subarray // Function for maximum product function max_product( $arr $n) { // Initialize maximum products // in forward and backward // directions $max_fwd = PHP_INT_MIN; $max_bkd = PHP_INT_MIN; // Initialize current product $max_till_now = 1; // max_fwd for maximum contiguous // product in forward direction // max_bkd for maximum contiguous // product in backward direction // iterating within forward direction // in array for ($i = 0; $i < $n; $i++) { // if arr[i]==0 it is // breaking condition // for contiguous subarray $max_till_now = $max_till_now * $arr[$i]; if ($max_till_now == 0) { $max_till_now = 1; continue; } // update max_fwd if ($max_fwd < $max_till_now) $max_fwd = $max_till_now; } $max_till_now = 1; // iterating within backward // direction in array for($i = $n - 1; $i >= 0; $i--) { $max_till_now = $max_till_now * $arr[$i]; if ($max_till_now == 0) { $max_till_now = 1; continue; } // update max_bkd if ($max_bkd < $max_till_now) $max_bkd = $max_till_now; } // return max of max_fwd // and max_bkd $res = max($max_fwd $max_bkd); // Product should not be negative. // (Product of an empty subarray is // considered as 0) return max($res 0); } // Driver Code $arr = array(-1 -2 -3 4); $n = count($arr); echo max_product($arr $n); // This code is contributed by anuj_67. ?> <script> // JavaScript program to find maximum product // subarray // Function for maximum product function max_product(arr n) { // Initialize maximum products in // forward and backward directions let max_fwd = Number.MIN_VALUE max_bkd = Number.MIN_VALUE; // Initialize current product let max_till_now = 1; // max_fwd for maximum contiguous // product in forward direction // max_bkd for maximum contiguous // product in backward direction // iterating within forward // direction in array for (let i = 0; i < n; i++) { // if arr[i]==0 it is breaking // condition for contiguous subarray max_till_now = max_till_now * arr[i]; if (max_till_now == 0) { max_till_now = 1; continue; } // update max_fwd if (max_fwd < max_till_now) max_fwd = max_till_now; } max_till_now = 1; // iterating within backward // direction in array for (let i = n - 1; i >= 0; i--) { max_till_now = max_till_now * arr[i]; if (max_till_now == 0) { max_till_now = 1; continue; } // update max_bkd if (max_bkd < max_till_now) max_bkd = max_till_now; } // return max of max_fwd and max_bkd let res = Math.max(max_fwd max_bkd); // Product should not be negative. // (Product of an empty subarray is // considered as 0) return Math.max(res 0); } let arr = [-1 -2 -3 4]; let n = arr.length; document.write(max_product(arr n) ); </script>
Sortir
24
Complexité temporelle : O(n)
Espace auxiliaire : O(1)
Notez que la solution ci-dessus nécessite deux parcours d'un tableau tandis que le solution précédente ne nécessite qu’un seul parcours.
méthode égale java