Dado un arreglo A[] que contiene enteros positivos y negativos, encuentre el subarreglo de producto máximo.
Ejemplos:
Input: A[] = { 6, -3, -10, 0, 2 } Output: 180 // The subarray is {6, -3, -10} Input: A[] = {-1, -3, -10, 0, 60 } Output: 60 // The subarray is {60} Input: A[] = { -2, -3, 0, -2, -40 } Output: 80 // The subarray is {-2, -40}
La idea es recorrer la array de izquierda a derecha manteniendo dos variables minVal y maxVal que representan el valor mínimo y máximo del producto hasta el i-ésimo índice de la array. Ahora, si el i-ésimo elemento de la array es negativo, eso significa que ahora los valores de minVal y maxVal se intercambiarán ya que el valor de maxVal se volverá mínimo al multiplicarlo por un número negativo. Ahora, compare minVal y maxVal.
El valor de minVal y maxVal depende del elemento de índice actual o del producto del elemento de índice actual y el minVal y maxVal anteriores, respectivamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find maximum product subarray #include <bits/stdc++.h> using namespace std; // Function to find maximum product subarray int maxProduct(int* arr, int n) { // Variables to store maximum and minimum // product till ith index. int minVal = arr[0]; int maxVal = arr[0]; int maxProduct = arr[0]; for (int i = 1; i < n; i++) { // When multiplied by -ve number, // maxVal becomes minVal // and minVal becomes maxVal. if (arr[i] < 0) swap(maxVal, minVal); // maxVal and minVal stores the // product of subarray ending at arr[i]. maxVal = max(arr[i], maxVal * arr[i]); minVal = min(arr[i], minVal * arr[i]); // Max Product of array. maxProduct = max(maxProduct, maxVal); } // Return maximum product found in array. return maxProduct; } // Driver Code int main() { int arr[] = { -1, -3, -10, 0, 60 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Maximum Subarray product is " << maxProduct(arr, n) << endl; return 0; }
Java
// Java program to find maximum product subarray import java.io.*; class GFG { // Function to find maximum product subarray static int maxProduct(int arr[], int n) { // Variables to store maximum and minimum // product till ith index. int minVal = arr[0]; int maxVal = arr[0]; int maxProduct = arr[0]; for (int i = 1; i < n; i++) { // When multiplied by -ve number, // maxVal becomes minVal // and minVal becomes maxVal. if (arr[i] < 0) { int temp = maxVal; maxVal = minVal; minVal =temp; } // maxVal and minVal stores the // product of subarray ending at arr[i]. maxVal = Math.max(arr[i], maxVal * arr[i]); minVal = Math.min(arr[i], minVal * arr[i]); // Max Product of array. maxProduct = Math.max(maxProduct, maxVal); } // Return maximum product found in array. return maxProduct; } // Driver Code public static void main (String[] args) { int arr[] = { -1, -3, -10, 0, 60 }; int n = arr.length; System.out.println( "Maximum Subarray product is " + maxProduct(arr, n)); } } // This code is contributed by anuj_67.
Python3
# Python 3 program to find maximum # product subarray # Function to find maximum # product subarray def maxProduct(arr, n): # Variables to store maximum and # minimum product till ith index. minVal = arr[0] maxVal = arr[0] maxProduct = arr[0] for i in range(1, n, 1): # When multiplied by -ve number, # maxVal becomes minVal # and minVal becomes maxVal. if (arr[i] < 0): temp = maxVal maxVal = minVal minVal = temp # maxVal and minVal stores the # product of subarray ending at arr[i]. maxVal = max(arr[i], maxVal * arr[i]) minVal = min(arr[i], minVal * arr[i]) # Max Product of array. maxProduct = max(maxProduct, maxVal) # Return maximum product # found in array. return maxProduct # Driver Code if __name__ == '__main__': arr = [-1, -3, -10, 0, 60] n = len(arr) print("Maximum Subarray product is", maxProduct(arr, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find // maximum product subarray using System; class GFG { // Function to find maximum // product subarray static int maxProduct(int []arr, int n) { // Variables to store // maximum and minimum // product till ith index. int minVal = arr[0]; int maxVal = arr[0]; int maxProduct = arr[0]; for (int i = 1; i < n; i++) { // When multiplied by -ve // number, maxVal becomes // minVal and minVal // becomes maxVal. if (arr[i] < 0) { int temp = maxVal; maxVal = minVal; minVal = temp; } // maxVal and minVal stores // the product of subarray // ending at arr[i]. maxVal = Math.Max(arr[i], maxVal * arr[i]); minVal = Math.Min(arr[i], minVal * arr[i]); // Max Product of array. maxProduct = Math.Max(maxProduct, maxVal); } // Return maximum product // found in array. return maxProduct; } // Driver Code public static void Main () { int []arr = {-1, -3, -10, 0, 60}; int n = arr.Length; Console.WriteLine("Maximum Subarray " + "product is " + maxProduct(arr, n)); } } // This code is contributed by anuj_67.
PHP
<?php // PHP program to find maximum // product subarray // Function to find maximum // product subarray function maxProduct(&$arr, $n) { // Variables to store maximum and // minimum product till ith index. $minVal = $arr[0]; $maxVal = $arr[0]; $maxProduct = $arr[0]; for ($i = 1; $i < $n; $i++) { // When multiplied by -ve number, // maxVal becomes minVal // and minVal becomes maxVal. if ($arr[$i] < 0) { $temp = $maxVal; $maxVal = $minVal; $minVal = $temp; } // maxVal and minVal stores the // product of subarray ending at arr[i]. $maxVal = max($arr[$i], $maxVal * $arr[$i]); $minVal = min($arr[$i], $minVal * $arr[$i]); // Max Product of array. $maxProduct = max($maxProduct, $maxVal); } // Return maximum product found in array. return $maxProduct; } // Driver Code $arr = array( -1, -3, -10, 0, 60 ); $n = sizeof($arr); echo "Maximum Subarray product is " . maxProduct($arr, $n) . "\n"; // This code is contributed by ita_c ?>
Javascript
<script> // Javascript program to find maximum product subarray // Function to find maximum product subarray function maxProduct(arr,n) { // Variables to store maximum and minimum // product till ith index. let minVal = arr[0]; let maxVal = arr[0]; let maxProduct = arr[0]; for (let i = 1; i < n; i++) { // When multiplied by -ve number, // maxVal becomes minVal // and minVal becomes maxVal. if (arr[i] < 0) { let temp = maxVal; maxVal = minVal; minVal =temp; } // maxVal and minVal stores the // product of subarray ending at arr[i]. maxVal = Math.max(arr[i], maxVal * arr[i]); minVal = Math.min(arr[i], minVal * arr[i]); // Max Product of array. maxProduct = Math.max(maxProduct, maxVal); } // Return maximum product found in array. return maxProduct; } // Driver Code let arr=[ -1, -3, -10, 0, 60 ]; let n = arr.length; document.write( "Maximum Subarray product is " + maxProduct(arr, n)); // This code is contributed by rag2127 </script>
Maximum Sub array product is 60
Complejidad de Tiempo : O( n )
Espacio Auxiliar : O( 1 )
Artículos Relacionados :
- Subarreglo de producto máximo | Serie 1
- Subarreglo de producto máximo | Conjunto 2 (usando dos transversales)
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA