算法：找出最大乘积子数组|s2（使用两次遍历）

2021年3月12日13:52:45 发表评论 689 次浏览

本文概述

``````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.``````

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

.

1. 从左到右遍历的最大乘积。
2. 从右到左遍历的最大乘积

C ++

``````// C++ program to find maximum product subarray
#include<bits/stdc++.h>
using namespace std;

// Function for maximum product
int max_product( int arr[], int n)
{
// Initialize maximum products in forward and
// backward directions
int max_fwd = INT_MIN, max_bkd = INT_MIN;

// Initialize current product
int max_till_now = 1;

//check if zero is present in an array or not
bool isZero= false ;

// 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 ;
}
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 ( 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 =  max(max_fwd, max_bkd);

// Product should not be nagative.
// (Product of an empty subarray is
// considered as 0)
if (isZero)
return max(res, 0);

return res;
}

// Driver Program to test above function
int main()
{
int arr[] = {-1, -2, -3, 4};
int n = sizeof (arr)/ sizeof (arr[0]);
cout << max_product(arr, n) << endl;
return 0;
}``````

Java

``````// 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 nagative.
// (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

``````# 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 nagative.
# (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#

``````// 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 nagative.
// (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

``````<?php
// 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 nagative.
// (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.
?>``````

``24``

O(1)