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>
Producción:
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