# 算法设计：最大子数组的乘积

2021年3月11日17:07:05 发表评论 313 次浏览

## 本文概述

``````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, -3, 0, -2, -40}
Output:   80  // The subarray is {-2, -40}``````

## C ++

``````// C++ program to find Maximum Product Subarray
#include <bits/stdc++.h>
using namespace std;

/* 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 = 1;
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 == 1)
return 0;
return max_so_far;
}

// Driver code
int main()
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
int n = sizeof (arr) / sizeof (arr);
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 = 1;
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 == 1)
return 0;
return max_so_far;

return max_so_far;
}

// Driver Program to test above function
int main()
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
int n = sizeof (arr) / sizeof (arr);
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 = 1 ;
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 == 1 )
return 0 ;
return max_so_far;
}

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*/``````

## python

``````# 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 = 1
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 = = 1 :
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 = 1;
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 == 1)
return 0;

return max_so_far;
}

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 = 1;
\$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 ==1) 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 );
echo ( "Maximum Sub array product is " );
echo (maxSubarrayProduct( \$arr , \$n ));

// This code is contributed by nitin mittal
?>``````

``Maximum Sub array product is 112``

O(1) 