本文概述

• 建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
• C ++
• Java
• Python3
• C#
• 的PHP

给定一个同时包含正整数和负整数的数组, 请最大乘积子数组。预期的时间复杂度为O(n), 并且只能使用O(1)的额外空间。
例子 ：

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. 从右到左遍历的最大乘积

【算法（找出最大乘积子数组|s2（使用两次遍历））】例如, 考虑上面的第三个样本输入{-1, -2, -3, 4}。如果仅向前移动数组(将-1作为输出的一部分), 则最大乘积将为2。如果我们向后移动数组(将4作为输出的一部分), 则最大乘积将为24。 {-2, -3, 4}。
重要的一件事是处理0。每当我们看到0时, 就需要计算新的正向(或反向)和。
下面是上述想法的实现：
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 ; continueif (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)
请注意, 上述解决方案需要两次遍历数组, 而先前的解决方案只需要一个遍历。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  电商模式 mv是电商的什么，电商平台
• 

  蓝光驱蚊灯可以和人在一起吗
• 

  兼职跨境电商怎么样 跨境电商可以做什么兼职，哪个跨境电商平台适合兼职做
• 

  香菇酿肉的方法
• 

  方牌玉件的佩戴方法 方形玉牌吊坠怎么佩戴
• 

  纳兰词全集及赏析 温室的花
• 

  cdrx8安装提示已安装另一个版本解决方法
• 

  win10自带硬盘安装系统怎么安装，win10自带硬盘安装系统怎么安装不了
• 

  微信没声音怎么回事 没有声音解决办法
• 

  智齿|智齿发炎，疼痛得厉害还不能拔牙，有什么应急措施？
• 

  人工智能论文，人工智能的发展前景及其应用的论文怎么写
• 

  北太行在什么地方 北太行在哪里
• 

  博世壁挂炉德国还土耳其原因？
• 

  2023款一汽大众辉腾 一汽大众辉腾字母
• 

  3点到5点醒是癌症征兆有科学依据吗
• 

  樟脑丸可以放床下吗
• 

  干燥综合征如何治疗?
• 

  建设自由贸易区的意义 12个自贸试验区共有哪些
• 

  儿童可以使用免洗洗手液吗
• 

  登鹳雀楼古诗看到了哪四种景物？

• Python中的图像处理（缩放，旋转，移位和边缘检测）
• PHP gmp_com()函数用法介绍
• 推荐（如何预防和避免死锁（））
• 为什么使用Quill（ — Quill富文本编辑器快速入门中文文档）
• mysql开发深入浅出（数据库导出和导入数据操作详细操作步骤）
• mysql开发细节（使用自动递增序列以及处理重复数据）
• mysql复制表操作和数据库元数据介绍
• mysql alter命令和mysql索引介绍
• mysql事务操作介绍和临时表的使用