Dada una array que contiene enteros positivos y negativos, encuentre el producto del subarreglo de producto máximo. La complejidad del tiempo esperado es O(n) y solo se puede usar O(1) espacio extra.
Ejemplos:
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[] = {-2, -40, 0, -2, -3}
Output: 80 // The subarray is {-2, -40}
Solución ingenua:
La idea es recorrer todos los subarreglos contiguos, encontrar el producto de cada uno de estos subarreglos y devolver el producto máximo de estos resultados.
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;
/* Returns the product of max product subarray.*/
int maxSubarrayProduct(int arr[], int n)
{
// Initializing result
int result = arr[0];
for (int i = 0; i < n; i++)
{
int mul = arr[i];
// traversing in current subarray
for (int j = i + 1; j < n; j++)
{
// updating result every time
// to keep an eye over the maximum product
result = max(result, mul);
mul *= arr[j];
}
// updating the result for (n-1)th index.
result = max(result, mul);
}
return result;
}
// Driver code
int main()
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum Sub array product is "
<< maxSubarrayProduct(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to find Maximum Product Subarray
#include <stdio.h>
// Find maximum between two numbers.
int max(int num1, int num2)
{
return (num1 > num2) ? num1 : num2;
}
/* Returns the product of max product subarray.*/
int maxSubarrayProduct(int arr[], int n)
{
// Initializing result
int result = arr[0];
for (int i = 0; i < n; i++) {
int mul = arr[i];
// traversing in current subarray
for (int j = i + 1; j < n; j++) {
// updating result every time
// to keep an eye over the maximum product
result = max(result, mul);
mul *= arr[j];
}
// updating the result for (n-1)th index.
result = max(result, mul);
}
return result;
}
// Driver code
int main()
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Maximum Sub array product is %d ", maxSubarrayProduct(arr, n));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to find maximum product subarray
import java.io.*;
class GFG {
/* Returns the product of max product subarray.*/
static int maxSubarrayProduct(int arr[])
{
// Initializing result
int result = arr[0];
int n = arr.length;
for (int i = 0; i < n; i++) {
int mul = arr[i];
// traversing in current subarray
for (int j = i + 1; j < n; j++) {
// updating result every time to keep an eye
// over the maximum product
result = Math.max(result, mul);
mul *= arr[j];
}
// updating the result for (n-1)th index.
result = Math.max(result, mul);
}
return result;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
System.out.println("Maximum Sub array product is "
+ maxSubarrayProduct(arr));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program to find Maximum Product Subarray
# Returns the product of max product subarray.
def maxSubarrayProduct(arr, n):
# Initializing result
result = arr[0]
for i in range(n):
mul = arr[i]
# traversing in current subarray
for j in range(i + 1, n):
# updating result every time
# to keep an eye over the maximum product
result = max(result, mul)
mul *= arr[j]
# updating the result for (n-1)th index.
result = max(result, mul)
return result
# Driver code
arr = [ 1, -2, -3, 0, 7, -8, -2 ]
n = len(arr)
print("Maximum Sub array product is" , maxSubarrayProduct(arr, n))
# This code is contributed by divyeshrabadiya07
C#
// C# program to find maximum product subarray
using System;
class GFG{
// Returns the product of max product subarray
static int maxSubarrayProduct(int []arr)
{
// Initializing result
int result = arr[0];
int n = arr.Length;
for(int i = 0; i < n; i++)
{
int mul = arr[i];
// Traversing in current subarray
for(int j = i + 1; j < n; j++)
{
// Updating result every time
// to keep an eye over the
// maximum product
result = Math.Max(result, mul);
mul *= arr[j];
}
// Updating the result for (n-1)th index
result = Math.Max(result, mul);
}
return result;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, -2, -3, 0, 7, -8, -2 };
Console.Write("Maximum Sub array product is " +
maxSubarrayProduct(arr));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program to find Maximum Product Subarray
/* Returns the product of max product subarray.*/
function maxSubarrayProduct(arr, n)
{
// Initializing result
let result = arr[0];
for (let i = 0; i < n; i++)
{
let mul = arr[i];
// traversing in current subarray
for (let j = i + 1; j < n; j++)
{
// updating result every time
// to keep an eye over the maximum product
result = Math.max(result, mul);
mul *= arr[j];
}
// updating the result for (n-1)th index.
result = Math.max(result, mul);
}
return result;
}
// Driver code
let arr = [ 1, -2, -3, 0, 7, -8, -2 ];
let n = arr.length;
document.write("Maximum Sub array product is "
+ maxSubarrayProduct(arr, n));
// This code is contributed by Mayank Tyagi
</script>
Producción
Maximum Sub array product is 112
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Solución eficiente:
La siguiente solución asume que la array de entrada dada siempre tiene una salida positiva. La solución funciona para todos los casos mencionados anteriormente. No funciona para arreglos como {0, 0, -20, 0}, {0, 0, 0}… etc. La solución se puede modificar fácilmente para manejar este caso.
Es similar al problema de subarreglo contiguo de suma más grande . Lo único que se debe tener en cuenta aquí es que el producto máximo también se puede obtener mediante el producto mínimo (negativo) que termina con el elemento anterior multiplicado por este elemento. Por ejemplo, en el arreglo {12, 2, -3, -5, -6, -2}, cuando estamos en el elemento -2, el producto máximo es la multiplicación del producto mínimo que termina en -6 y -2.
Nota : si todos los elementos de la array son negativos, el producto máximo con el algoritmo anterior es 1. Entonces, si el producto máximo es 1, entonces tenemos que devolver el elemento máximo de una array.
C++
// C++ program to find Maximum Product Subarray
#include <bits/stdc++.h>
using namespace std;
/* Returns the product
of max product subarray.
*/
int maxSubarrayProduct(int arr[], int n)
{
// max positive product
// ending at the current position
int max_ending_here = 1;
// min negative product ending
// at the current position
int min_ending_here = 1;
// Initialize overall max product
int max_so_far = 0;
int flag = 0;
/* Traverse through the array.
Following values are
maintained after the i'th iteration:
max_ending_here is always 1 or
some positive product ending with arr[i]
min_ending_here is always 1 or
some negative product ending with arr[i] */
for (int i = 0; i < n; i++)
{
/* If this element is positive, update
max_ending_here. Update min_ending_here only if
min_ending_here is negative */
if (arr[i] > 0)
{
max_ending_here = max_ending_here * arr[i];
min_ending_here
= min(min_ending_here * arr[i], 1);
flag = 1;
}
/* If this element is 0, then the maximum product
cannot end here, make both max_ending_here and
min_ending_here 0
Assumption: Output is alway greater than or equal
to 1. */
else if (arr[i] == 0) {
max_ending_here = 1;
min_ending_here = 1;
}
/* If element is negative. This is tricky
max_ending_here can either be 1 or positive.
min_ending_here can either be 1 or negative.
next max_ending_here will always be prev.
min_ending_here * arr[i] ,next min_ending_here
will be 1 if prev max_ending_here is 1, otherwise
next min_ending_here will be prev max_ending_here *
arr[i] */
else {
int temp = max_ending_here;
max_ending_here
= max(min_ending_here * arr[i], 1);
min_ending_here = temp * arr[i];
}
// update max_so_far, if needed
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
if (flag == 0 && max_so_far == 0)
return 0;
/* if all the array elements are negative */
if (max_so_far == 1)
{
max_so_far = arr[0];
for(int i = 1; i < n; i++)
max_so_far = max(max_so_far, arr[i]);
}
return max_so_far;
}
// Driver code
int main()
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum Sub array product is "
<< maxSubarrayProduct(arr, n);
return 0;
}
// This is code is contributed by rathbhupendra
C
// C program to find Maximum Product Subarray
#include <stdio.h>
// Utility functions to get minimum of two integers
int min(int x, int y) { return x < y ? x : y; }
// Utility functions to get maximum of two integers
int max(int x, int y) { return x > y ? x : y; }
/* Returns the product of max product subarray.
Assumes that the given array always has a subarray
with product more than 1 */
int maxSubarrayProduct(int arr[], int n)
{
// max positive product
// ending at the current position
int max_ending_here = 1;
// min negative product ending
// at the current position
int min_ending_here = 1;
// Initialize overall max product
int max_so_far = 0;
int flag = 0;
/* Traverse through the array. Following values are
maintained after the i'th iteration:
max_ending_here is always 1 or some positive product
ending with arr[i]
min_ending_here is always 1 or some negative product
ending with arr[i] */
for (int i = 0; i < n; i++) {
/* If this element is positive, update
max_ending_here. Update min_ending_here only if
min_ending_here is negative */
if (arr[i] > 0) {
max_ending_here = max_ending_here * arr[i];
min_ending_here
= min(min_ending_here * arr[i], 1);
flag = 1;
}
/* If this element is 0, then the maximum product
cannot end here, make both max_ending_here and
min_ending_here 0
Assumption: Output is alway greater than or equal
to 1. */
else if (arr[i] == 0) {
max_ending_here = 1;
min_ending_here = 1;
}
/* If element is negative. This is tricky
max_ending_here can either be 1 or positive.
min_ending_here can either be 1 or negative.
next min_ending_here will always be prev.
max_ending_here * arr[i] next max_ending_here
will be 1 if prev min_ending_here is 1, otherwise
next max_ending_here will be prev min_ending_here *
arr[i] */
else {
int temp = max_ending_here;
max_ending_here
= max(min_ending_here * arr[i], 1);
min_ending_here = temp * arr[i];
}
// update max_so_far, if needed
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
if (flag == 0 && max_so_far == 0)
return 0;
return max_so_far;
return max_so_far;
}
// Driver code
int main()
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Maximum Sub array product is %d",
maxSubarrayProduct(arr, n));
return 0;
}
Java
// Java program to find maximum product subarray
import java.io.*;
class ProductSubarray {
// Utility functions to get
// minimum of two integers
static int min(int x, int y) {
return x < y ? x : y;
}
// Utility functions to get
// maximum of two integers
static int max(int x, int y) {
return x > y ? x : y;
}
/* Returns the product of
max product subarray.
Assumes that the given
array always has a subarray
with product more than 1 */
static int maxSubarrayProduct(int arr[])
{
int n = arr.length;
// max positive product
// ending at the current
// position
int max_ending_here = 1;
// min negative product
// ending at the current
// position
int min_ending_here = 1;
// Initialize overall max product
int max_so_far = 0;
int flag = 0;
/* Traverse through the array. Following
values are maintained after the ith iteration:
max_ending_here is always 1 or some positive product
ending with arr[i]
min_ending_here is always 1 or some negative product
ending with arr[i] */
for (int i = 0; i < n; i++)
{
/* If this element is positive, update
max_ending_here. Update min_ending_here only
if min_ending_here is negative */
if (arr[i] > 0)
{
max_ending_here = max_ending_here * arr[i];
min_ending_here
= min(min_ending_here * arr[i], 1);
flag = 1;
}
/* If this element is 0, then the maximum
product cannot end here, make both
max_ending_here and min_ending _here 0
Assumption: Output is alway greater than or
equal to 1. */
else if (arr[i] == 0)
{
max_ending_here = 1;
min_ending_here = 1;
}
/* If element is negative. This is tricky
max_ending_here can either be 1 or positive.
min_ending_here can either be 1 or negative.
next min_ending_here will always be prev.
max_ending_here * arr[i]
next max_ending_here will be 1 if prev
min_ending_here is 1, otherwise
next max_ending_here will be
prev min_ending_here * arr[i] */
else {
int temp = max_ending_here;
max_ending_here
= max(min_ending_here * arr[i], 1);
min_ending_here = temp * arr[i];
}
// update max_so_far, if needed
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
if (flag == 0 && max_so_far == 0)
return 0;
return max_so_far;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
System.out.println("Maximum Sub array product is "
+ maxSubarrayProduct(arr));
}
} /*This code is contributed by Devesh Agrawal*/
Python3
# Python program to find maximum product subarray
# Returns the product of max product subarray.
# Assumes that the given array always has a subarray
# with product more than 1
def maxsubarrayproduct(arr):
n = len(arr)
# max positive product ending at the current position
max_ending_here = 1
# min positive product ending at the current position
min_ending_here = 1
# Initialize maximum so far
max_so_far = 0
flag = 0
# Traverse throughout the array. Following values
# are maintained after the ith iteration:
# max_ending_here is always 1 or some positive product
# ending with arr[i]
# min_ending_here is always 1 or some negative product
# ending with arr[i]
for i in range(0, n):
# If this element is positive, update max_ending_here.
# Update min_ending_here only if min_ending_here is
# negative
if arr[i] > 0:
max_ending_here = max_ending_here * arr[i]
min_ending_here = min (min_ending_here * arr[i], 1)
flag = 1
# If this element is 0, then the maximum product cannot
# end here, make both max_ending_here and min_ending_here 0
# Assumption: Output is alway greater than or equal to 1.
elif arr[i] == 0:
max_ending_here = 1
min_ending_here = 1
# If element is negative. This is tricky
# max_ending_here can either be 1 or positive.
# min_ending_here can either be 1 or negative.
# next min_ending_here will always be prev.
# max_ending_here * arr[i]
# next max_ending_here will be 1 if prev
# min_ending_here is 1, otherwise
# next max_ending_here will be prev min_ending_here * arr[i]
else:
temp = max_ending_here
max_ending_here = max (min_ending_here * arr[i], 1)
min_ending_here = temp * arr[i]
if (max_so_far < max_ending_here):
max_so_far = max_ending_here
if flag == 0 and max_so_far == 0:
return 0
return max_so_far
# Driver function to test above function
arr = [1, -2, -3, 0, 7, -8, -2]
print ("Maximum product subarray is", maxsubarrayproduct(arr))
# This code is contributed by Devesh Agrawal
C#
// C# program to find maximum product subarray
using System;
class GFG {
// Utility functions to get minimum of two integers
static int min(int x, int y)
{
return x < y ? x : y;
}
// Utility functions to get maximum of two integers
static int max(int x, int y)
{
return x > y ? x : y;
}
/* Returns the product of max product subarray.
Assumes that the given array always has a subarray
with product more than 1 */
static int maxSubarrayProduct(int[] arr)
{
int n = arr.Length;
// max positive product ending at the current
// position
int max_ending_here = 1;
// min negative product ending at the current
// position
int min_ending_here = 1;
// Initialize overall max product
int max_so_far = 0;
int flag = 0;
/* Traverse through the array. Following
values are maintained after the ith iteration:
max_ending_here is always 1 or some positive
product ending with arr[i] min_ending_here is
always 1 or some negative product ending
with arr[i] */
for (int i = 0; i < n; i++)
{
/* If this element is positive, update
max_ending_here. Update min_ending_here
only if min_ending_here is negative */
if (arr[i] > 0) {
max_ending_here = max_ending_here * arr[i];
min_ending_here = min(min_ending_here
* arr[i],
1);
flag = 1;
}
/* If this element is 0, then the maximum
product cannot end here, make both
max_ending_here and min_ending_here 0
Assumption: Output is alway greater than or
equal to 1. */
else if (arr[i] == 0)
{
max_ending_here = 1;
min_ending_here = 1;
}
/* If element is negative. This is tricky
max_ending_here can either be 1 or positive.
min_ending_here can either be 1 or negative.
next min_ending_here will always be prev.
max_ending_here * arr[i]
next max_ending_here will be 1 if prev
min_ending_here is 1, otherwise
next max_ending_here will be
prev min_ending_here * arr[i] */
else
{
int temp = max_ending_here;
max_ending_here = max(min_ending_here
* arr[i],
1);
min_ending_here = temp * arr[i];
}
// update max_so_far, if needed
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
if (flag == 0 && max_so_far == 0)
return 0;
return max_so_far;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
Console.WriteLine("Maximum Sub array product is "
+ maxSubarrayProduct(arr));
}
}
/*This code is contributed by vt_m*/
PHP
<?php
// php program to find Maximum Product
// Subarray
// Utility functions to get minimum of
// two integers
function minn ($x, $y)
{
return $x < $y? $x : $y;
}
// Utility functions to get maximum of
// two integers
function maxx ($x, $y)
{
return $x > $y? $x : $y;
}
/* Returns the product of max product
subarray. Assumes that the given array
always has a subarray with product
more than 1 */
function maxSubarrayProduct($arr, $n)
{
// max positive product ending at
// the current position
$max_ending_here = 1;
// min negative product ending at
// the current position
$min_ending_here = 1;
// Initialize overall max product
$max_so_far = 0;
$flag = 0;
/* Traverse through the array.
Following values are maintained
after the i'th iteration:
max_ending_here is always 1 or
some positive product ending with
arr[i] min_ending_here is always
1 or some negative product ending
with arr[i] */
for ($i = 0; $i < $n; $i++)
{
/* If this element is positive,
update max_ending_here. Update
min_ending_here only if
min_ending_here is negative */
if ($arr[$i] > 0)
{
$max_ending_here =
$max_ending_here * $arr[$i];
$min_ending_here =
min ($min_ending_here
* $arr[$i], 1);
$flag = 1;
}
/* If this element is 0, then the
maximum product cannot end here,
make both max_ending_here and
min_ending_here 0
Assumption: Output is alway
greater than or equal to 1. */
else if ($arr[$i] == 0)
{
$max_ending_here = 1;
$min_ending_here = 1;
}
/* If element is negative. This
is tricky max_ending_here can
either be 1 or positive.
min_ending_here can either be 1 or
negative. next min_ending_here will
always be prev. max_ending_here *
arr[i] next max_ending_here will be
1 if prev min_ending_here is 1,
otherwise next max_ending_here will
be prev min_ending_here * arr[i] */
else
{
$temp = $max_ending_here;
$max_ending_here =
max ($min_ending_here
* $arr[$i], 1);
$min_ending_here =
$temp * $arr[$i];
}
// update max_so_far, if needed
if ($max_so_far < $max_ending_here)
$max_so_far = $max_ending_here;
}
if($flag==0 && $max_so_far==0) return 0;
return $max_so_far;
}
// Driver Program to test above function
$arr = array(1, -2, -3, 0, 7, -8, -2);
$n = sizeof($arr) / sizeof($arr[0]);
echo("Maximum Sub array product is ");
echo (maxSubarrayProduct($arr, $n));
// This code is contributed by nitin mittal
?>
Javascript
<script>
// JavaScript program to find
// Maximum Product Subarray
/* Returns the product
of max product subarray.
Assumes that the given
array always has a subarray
with product more than 1 */
function maxSubarrayProduct(arr, n)
{
// max positive product
// ending at the current position
let max_ending_here = 1;
// min negative product ending
// at the current position
let min_ending_here = 1;
// Initialize overall max product
let max_so_far = 0;
let flag = 0;
/* Traverse through the array.
Following values are
maintained after the i'th iteration:
max_ending_here is always 1 or
some positive product ending with arr[i]
min_ending_here is always 1 or
some negative product ending with arr[i] */
for (let i = 0; i < n; i++)
{
/* If this element is positive, update
max_ending_here. Update min_ending_here only if
min_ending_here is negative */
if (arr[i] > 0)
{
max_ending_here = max_ending_here * arr[i];
min_ending_here
= Math.min(min_ending_here * arr[i], 1);
flag = 1;
}
/* If this element is 0, then the maximum product
cannot end here, make both max_ending_here and
min_ending_here 0
Assumption: Output is alway greater than or equal
to 1. */
else if (arr[i] == 0) {
max_ending_here = 1;
min_ending_here = 1;
}
/* If element is negative. This is tricky
max_ending_here can either be 1 or positive.
min_ending_here can either be 1 or negative.
next max_ending_here will always be prev.
min_ending_here * arr[i] ,next min_ending_here
will be 1 if prev max_ending_here is 1, otherwise
next min_ending_here will be prev max_ending_here *
arr[i] */
else {
let temp = max_ending_here;
max_ending_here
= Math.max(min_ending_here * arr[i], 1);
min_ending_here = temp * arr[i];
}
// update max_so_far, if needed
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
if (flag == 0 && max_so_far == 0)
return 0;
return max_so_far;
}
// Driver program
let arr = [ 1, -2, -3, 0, 7, -8, -2 ];
let n = arr.length;
document.write("Maximum Sub array product is " +
maxSubarrayProduct(arr,n));
</script>
Producción
Maximum Sub array product is 112
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Solución eficiente:
La solución anterior asume que siempre hay un resultado positivo para la array dada, lo que no funciona en los casos en que la array contiene solo elementos no positivos como {0, 0, -20, 0}, {0, 0, 0}… etc. La solución modificada también es similar al problema de subarreglo contiguo de suma más grande que utiliza el algoritmo de Kadane. Para facilitar la comprensión, no estamos usando ninguna bandera como la solución anterior. Aquí usamos 3 variables llamadas max_so_far, max_ending_here y min_ending_here . Para cada índice, el número máximo que termina en ese índice será el máximo (arr[i], max_ending_here * arr[i], min_ending_here[i]*arr[i]) . De manera similar, el número mínimo que termina aquí será el mínimo de estos 3. Así obtenemos el valor final para el subarreglo de producto máximo.
C++
// C++ program to find Maximum Product Subarray
#include <bits/stdc++.h>
using namespace std;
/* Returns the product
of max product subarray. */
int maxSubarrayProduct(int arr[], int n)
{
// max positive product
// ending at the current position
int max_ending_here = arr[0];
// min negative product ending
// at the current position
int min_ending_here = arr[0];
// Initialize overall max product
int max_so_far = arr[0];
/* Traverse through the array.
the maximum product subarray ending at an index
will be the maximum of the element itself,
the product of element and max product ending previously
and the min product ending previously. */
for (int i = 1; i < n; i++) {
int temp = max({ arr[i], arr[i] * max_ending_here,
arr[i] * min_ending_here });
min_ending_here
= min({ arr[i], arr[i] * max_ending_here,
arr[i] * min_ending_here });
max_ending_here = temp;
max_so_far = max(max_so_far, max_ending_here);
}
return max_so_far;
}
// Driver code
int main()
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum Sub array product is "
<< maxSubarrayProduct(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to find Maximum Product Subarray
#include <stdio.h>
// Find maximum between two numbers.
int max(int num1, int num2)
{
return (num1 > num2) ? num1 : num2;
}
// Find minimum between two numbers.
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
/* Returns the product of max product subarray. */
int maxSubarrayProduct(int arr[], int n)
{
// max positive product
// ending at the current position
int max_ending_here = arr[0];
// min negative product ending
// at the current position
int min_ending_here = arr[0];
// Initialize overall max product
int max_so_far = arr[0];
/* Traverse through the array.
the maximum product subarray ending at an index
will be the maximum of the element itself,
the product of element and max product ending previously
and the min product ending previously. */
for (int i = 1; i < n; i++) {
int temp = max(max(arr[i], arr[i] * max_ending_here),
arr[i] * min_ending_here);
min_ending_here = min(min(arr[i], arr[i] * max_ending_here),
arr[i] * min_ending_here);
max_ending_here = temp;
max_so_far = max(max_so_far, max_ending_here);
}
return max_so_far;
}
// Driver code
int main()
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Maximum Sub array product is %d",
maxSubarrayProduct(arr, n));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
// Java program to find Maximum Product Subarray
// Returns the product
// of max product subarray.
static int maxSubarrayProduct(int arr[],int n){
// max positive product
// ending at the current position
int max_ending_here = arr[0];
// min negative product ending
// at the current position
int min_ending_here = arr[0];
// Initialize overall max product
int max_so_far = arr[0];
// /* Traverse through the array.
// the maximum product subarray ending at an index
// will be the maximum of the element itself,
// the product of element and max product ending previously
// and the min product ending previously. */
for(int i=1;i<n;i++){
int temp = Math.max(Math.max(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here);
min_ending_here = Math.min(Math.min(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here);
max_ending_here = temp;
max_so_far = Math.max(max_so_far, max_ending_here);
}
return max_so_far;
}
// Driver code
public static void main(String args[])
{
int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
int n = arr.length;
System.out.printf("Maximum Sub array product is %d",maxSubarrayProduct(arr, n));
}
}
// This code is contributed by shinjanpatra
Python3
# Python3 program to find Maximum Product Subarray
# Returns the product
# of max product subarray.
def maxSubarrayProduct(arr, n):
# max positive product
# ending at the current position
max_ending_here = arr[0]
# min negative product ending
# at the current position
min_ending_here = arr[0]
# Initialize overall max product
max_so_far = arr[0]
# /* Traverse through the array.
# the maximum product subarray ending at an index
# will be the maximum of the element itself,
# the product of element and max product ending previously
# and the min product ending previously. */
for i in range(1, n):
temp = max(max(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here)
min_ending_here = min(min(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here)
max_ending_here = temp
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
# Driver code
arr = [ 1, -2, -3, 0, 7, -8, -2 ]
n = len(arr)
print(f"Maximum Sub array product is {maxSubarrayProduct(arr, n)}")
# This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript program to find Maximum Product Subarray
/* Returns the product
of max product subarray. */
function maxSubarrayProduct(arr, n)
{
// max positive product
// ending at the current position
let max_ending_here = arr[0];
// min negative product ending
// at the current position
let min_ending_here = arr[0];
// Initialize overall max product
let max_so_far = arr[0];
/* Traverse through the array.
the maximum product subarray ending at an index
will be the maximum of the element itself,
the product of element and max product ending previously
and the min product ending previously. */
for (let i = 1; i < n; i++)
{
let temp = Math.max(Math.max(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here);
min_ending_here = Math.min(Math.min(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here);
max_ending_here = temp;
max_so_far = Math.max(max_so_far, max_ending_here);
}
return max_so_far;
}
// Driver code
let arr = [ 1, -2, -3, 0, 7, -8, -2 ]
let n = arr.length
document.write("Maximum Sub array product is "+maxSubarrayProduct(arr, n));
// This code is contributed by shinjanpatra
</script>
C#
// C# program to find maximum product subarray
using System;
class GFG {
/* Returns the product of max product subarray.
Assumes that the given array always has a subarray
with product more than 1 */
static int maxSubarrayProduct(int[] arr)
{
// max positive product
// ending at the current position
int max_ending_here = arr[0];
// min negative product ending
// at the current position
int min_ending_here = arr[0];
// Initialize overall max product
int max_so_far = arr[0];
/* Traverse through the array.
the maximum product subarray ending at an index
will be the maximum of the element itself,
the product of element and max product ending previously
and the min product ending previously. */
for(int i=1;i<arr.Length;i++)
{
int temp = Math.Max(Math.Max(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here);
min_ending_here = Math.Min(Math.Min(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here);
max_ending_here = temp;
max_so_far = Math.Max(max_so_far, max_ending_here);
}
return max_so_far;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
Console.WriteLine("Maximum Sub array product is "
+ maxSubarrayProduct(arr));
}
}
// This code is contributed by CodeWithMini
Producción
Maximum Sub array product is 112
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Este artículo fue compilado por Dheeraj Jain y revisado por el equipo de GeeksforGeeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA