Având în vedere o matrice care conține atât numere întregi pozitive, cât și negative, găsiți produsul subgrupului de produse maxime. Complexitatea timpului așteptat este O(n) și poate fi folosit doar spațiu suplimentar O(1).
caracter java la int
Exemple:
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. Am discutat despre o soluție a acestei probleme Aici .
În această postare se discută o soluție interesantă. Ideea se bazează pe faptul că produsul maxim total este de maximum două:
- Produs maxim în traversarea de la stânga la dreapta.
- Produs maxim în traversarea de la dreapta la stânga
De exemplu, luați în considerare cel de-al treilea eșantion de intrare de mai sus {-1 -2 -3 4}. Dacă parcurgem matricea numai în direcția înainte (considerând -1 ca parte a ieșirii) produsul maxim va fi 2. Dacă parcurgem matricea în direcția înapoi (considerând 4 ca parte a ieșirii) produsul maxim va fi 24 adică; { -2 -3 4}.
Un lucru important este să gestionați 0-urile. Trebuie să calculăm o sumă proaspătă înainte (sau înapoi) ori de câte ori vedem 0.
Mai jos este implementarea ideii de mai sus:
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>
Ieșire
24
Complexitatea timpului: O(n)
Spațiu auxiliar: O(1)
Rețineți că soluția de mai sus necesită două traversări ale unui tablou în timp ce soluție anterioară necesită o singură traversare.