给定一个包含正整数和负整数的数组，求最大乘积子数组的乘积。预期的时间复杂度为O（n），并且只能使用O（1）个额外空间。最大乘积可以是正、负或零。
null
例如：
Input : arr[] = {-2, -3, 0, -2, -40}Output : 80Subarray : arr[3..4] i.e.{-2, -40}Input : arr[] = {0, -4, 0, -2}Output : 0
我们已经详细讨论了这个问题 最大乘积子阵 ，但有一个限制，即结果只能是正面的。对于最大乘积为负或为零的情况，变量maxval（当前元素的最大乘积）和minval（当前元素的最小乘积）的值必须更新如下：
- 当arr[i]为正值时： 由于maxval是最大可能值，只需将arr[i]与maxval相乘即可获得新的maxval。minval是最小可能的负积。如果之前的值为负值，则只需将其与arr[i]相乘即可。如果其值为1，则将其保留为1。
- 当arr[i]为0时： 考虑测试用例：ARR[]= { 0，-4, 0，-2 }。在这种情况下，最大乘积为0。为了在我们的算法中解释这种情况，只要arr[i]为零，就用0而不是1更新maxval。任何数字与零的乘积都是零。考虑另一个测试用例，ARR[]= { 0, 1, 2 }。 如果maxval在当前迭代后保持为零（根据上述步骤），并且下一个元素为正，则结果将为零，而不是正元素。要考虑在每次迭代结束时检查Max是否为零。 如果为0，则将其设置为1。将minval更新为1作为子数组乘积，其中零作为元素将为零，这将导致丢失最小可能值。因此，通过将minval设置为1，即重新开始乘积计算，将该零从子数组中排除。
- 当arr[i]为负值时： maxval的新值是previous minval*arr[i]，minval的新值是previous maxval*arr[i]。在更新maxval之前，将其以前的值存储在prevMax中，以用于更新minval。
实施：
C++
// C++ program to find maximum subarray product. #include <bits/stdc++.h> using namespace std; // Function to find maximum subarray product. int findMaxProduct( int arr[], int n) { int i; // As maximum product can be negative, so // initialize ans with minimum integer value. int ans = INT_MIN; // Variable to store maximum product until // current value. int maxval = 1; // Variable to store minimum product until // current value. int minval = 1; // Variable used during updation of maximum // product and minimum product. int prevMax; for (i = 0; i < n; i++) { // If current element is positive, update // maxval. Update minval if it is // negative. if (arr[i] > 0) { maxval = maxval * arr[i]; minval = min(1, minval * arr[i]); } // If current element is zero, maximum // product cannot end at current element. // Update minval with 1 and maxval with 0. // maxval is updated to 0 as in case all // other elements are negative, then maxval // is 0. else if (arr[i] == 0) { minval = 1; maxval = 0; } // If current element is negative, then new // value of maxval is previous minval*arr[i] // and new value of minval is previous // maxval*arr[i]. Before updating maxval, // store its previous value in prevMax to // be used to update minval. else if (arr[i] < 0) { prevMax = maxval; maxval = minval * arr[i]; minval = prevMax * arr[i]; } // Update ans if necessary. ans = max(ans, maxval); // If maxval is zero, then to calculate // product for next iteration, it should // be set to 1 as maximum product // subarray does not include 0. // The minimum possible value // to be considered in maximum product // subarray is already stored in minval, // so when maxval is negative it is set to 1. if (maxval <= 0) { maxval = 1; } } return ans; } int main() { int arr[] = { 0, -4, 0, -2 }; int n = sizeof (arr) / sizeof (arr[0]); cout << findMaxProduct(arr, n); return 0; } |
JAVA
// Java program to find maximum subarray product. class GFG{ // Function to find maximum subarray product. static int findMaxProduct( int arr[], int n) { int i; // As maximum product can be negative, so // initialize ans with minimum integer value. int ans = Integer.MIN_VALUE; // Variable to store maximum product until // current value. int maxval = 1 ; // Variable to store minimum product until // current value. int minval = 1 ; // Variable used during updation of maximum // product and minimum product. int prevMax; for (i = 0 ; i < n; i++) { // If current element is positive, update // maxval. Update minval if it is // negative. if (arr[i] > 0 ) { maxval = maxval * arr[i]; minval = Math.min( 1 , minval * arr[i]); } // If current element is zero, maximum // product cannot end at current element. // Update minval with 1 and maxval with 0. // maxval is updated to 0 as in case all // other elements are negative, then maxval // is 0. else if (arr[i] == 0 ) { minval = 1 ; maxval = 0 ; } // If current element is negative, then new // value of maxval is previous minval*arr[i] // and new value of minval is previous // maxval*arr[i]. Before updating maxval, // store its previous value in prevMax to // be used to update minval. else if (arr[i] < 0 ) { prevMax = maxval; maxval = minval * arr[i]; minval = prevMax * arr[i]; } // Update ans if necessary. ans = Math.max(ans, maxval); // If maxval is zero, then to calculate // product for next iteration, it should // be set to 1 as maximum product // subarray does not include 0. // The minimum possible value // to be considered in maximum product // subarray is already stored in minval, // so when maxval is negative it is set to 1. if (maxval <= 0 ) { maxval = 1 ; } } return ans; } public static void main(String[] args) { int arr[] = { 0 , - 4 , 0 , - 2 }; int n = arr.length; System.out.println(findMaxProduct(arr, n)); } } |
Python3
# Python3 program to find maximum # subarray product. # Function to find maximum # subarray product. def findMaxProduct(arr, n): # As maximum product can be negative, # so initialize ans with minimum # integer value. ans = - float ( 'inf' ) # Variable to store maximum product # until current value. maxval = 1 # Variable to store minimum product # until current value. minval = 1 for i in range ( 0 , n): # If current element is positive, # update maxval. Update minval # if it is negative. if arr[i] > 0 : maxval = maxval * arr[i] minval = min ( 1 , minval * arr[i]) # If current element is zero, maximum # product cannot end at current element. # Update minval with 1 and maxval with 0. # maxval is updated to 0 as in case all # other elements are negative, then # maxval is 0. elif arr[i] = = 0 : minval = 1 maxval = 0 # If current element is negative, # then new value of maxval is previous # minval*arr[i] and new value of minval # is previous maxval*arr[i]. Before # updating maxval, store its previous # value in prevMax to be used to # update minval. elif arr[i] < 0 : prevMax = maxval maxval = minval * arr[i] minval = prevMax * arr[i] # Update ans if necessary. ans = max (ans, maxval) # If maxval is zero, then to calculate # product for next iteration, it should # be set to 1 as maximum product subarray # does not include 0. The minimum possible # value to be considered in maximum product # subarray is already stored in minval, # so when maxval is negative it is set to 1. if maxval < = 0 : maxval = 1 return ans # Driver Code if __name__ = = "__main__" : arr = [ 0 , - 4 , 0 , - 2 ] n = len (arr) print (findMaxProduct(arr, n)) # This code is contributed # by Rituraj Jain |
C#
// C# program to find maximum subarray product. using System; class GFG { // Function to find maximum subarray product. static int findMaxProduct( int [] arr, int n) { int i; // As maximum product can be negative, so // initialize ans with minimum integer value. int ans = Int32.MinValue; // Variable to store maximum product until // current value. int maxval = 1; // Variable to store minimum product until // current value. int minval = 1; // Variable used during updation of maximum // product and minimum product. int prevMax; for (i = 0; i < n; i++) { // If current element is positive, update // maxval. Update minval if it is // negative. if (arr[i] > 0) { maxval = maxval * arr[i]; minval = Math.Min(1, minval * arr[i]); } // If current element is zero, maximum // product cannot end at current element. // Update minval with 1 and maxval with 0. // maxval is updated to 0 as in case all // other elements are negative, then maxval // is 0. else if (arr[i] == 0) { minval = 1; maxval = 0; } // If current element is negative, then new // value of maxval is previous minval*arr[i] // and new value of minval is previous // maxval*arr[i]. Before updating maxval, // store its previous value in prevMax to // be used to update minval. else if (arr[i] < 0) { prevMax = maxval; maxval = minval * arr[i]; minval = prevMax * arr[i]; } // Update ans if necessary. ans = Math.Max(ans, maxval); // If maxval is zero, then to calculate // product for next iteration, it should // be set to 1 as maximum product // subarray does not include 0. // The minimum possible value // to be considered in maximum product // subarray is already stored in minval, // so when maxval is negative it is set to 1. if (maxval <= 0) { maxval = 1; } } return ans; } // Driver Code public static void Main() { int [] arr = { 0, -4, 0, -2 }; int n = arr.Length; Console.WriteLine(findMaxProduct(arr, n)); } } // This code is contributed // by Akanksha Rai |
PHP
<?php // PHP program to find maximum // subarray product. // Function to find maximum // subarray product. function findMaxProduct(& $arr , $n ) { // As maximum product can be negative, so // initialize ans with minimum integer value. $ans = 0; // Variable to store maximum product // until current value. $maxval = 1; // Variable to store minimum product // until current value. $minval = 1; // Variable used during updation of // maximum product and minimum product. // is prevMax for ( $i = 0; $i < $n ; $i ++) { // If current element is positive, update // maxval. Update minval if it is // negative. if ( $arr [ $i ] > 0) { $maxval = $maxval * $arr [i]; $minval = min(1, $minval * $arr [ $i ]); } // If current element is zero, maximum // product cannot end at current element. // Update minval with 1 and maxval with 0. // maxval is updated to 0 as in case all // other elements are negative, then maxval // is 0. else if ( $arr [ $i ] == 0) { $minval = 1; $maxval = 0; } // If current element is negative, then new // value of maxval is previous minval*arr[i] // and new value of minval is previous // maxval*arr[i]. Before updating maxval, // store its previous value in prevMax to // be used to update minval. else if ( $arr [ $i ] < 0) { $prevMax = $maxval ; $maxval = $minval * $arr [ $i ]; $minval = $prevMax * $arr [ $i ]; } // Update ans if necessary. $ans = max( $ans , $maxval ); // If maxval is zero, then to calculate // product for next iteration, it should // be set to 1 as maximum product // subarray does not include 0. // The minimum possible value // to be considered in maximum product // subarray is already stored in minval, // so when maxval is negative it is set to 1. if ( $maxval <= 0) { $maxval = 1; } } return $ans ; } // Driver Code $arr = array ( 0, -4, 0, -2 ); $n = sizeof( $arr ); echo findMaxProduct( $arr , $n ); // This code is contributed by ita_c ?> |
Javascript
<script> // JavaScript program to find maximum subarray product. // Function to find maximum subarray product. function findMaxProduct(arr, n) { let i; // As maximum product can be negative, so // initialize ans with minimum integer value. let ans = -1; // Variable to store maximum product until // current value. let maxval = 1; // Variable to store minimum product until // current value. let minval = 1; // Variable used during updation of maximum // product and minimum product. let prevMax; for (i = 0; i < n; i++) { // If current element is positive, update // maxval. Update minval if it is // negative. if (arr[i] > 0) { maxval = maxval * arr[i]; minval = Math.min(1, minval * arr[i]); } // If current element is zero, maximum // product cannot end at current element. // Update minval with 1 and maxval with 0. // maxval is updated to 0 as in case all // other elements are negative, then maxval // is 0. else if (arr[i] == 0) { minval = 1; maxval = 0; } // If current element is negative, then new // value of maxval is previous minval*arr[i] // and new value of minval is previous // maxval*arr[i]. Before updating maxval, // store its previous value in prevMax to // be used to update minval. else if (arr[i] < 0) { prevMax = maxval; maxval = minval * arr[i]; minval = prevMax * arr[i]; } // Update ans if necessary. ans = Math.max(ans, maxval); // If maxval is zero, then to calculate // product for next iteration, it should // be set to 1 as maximum product // subarray does not include 0. // The minimum possible value // to be considered in maximum product // subarray is already stored in minval, // so when maxval is negative it is set to 1. if (maxval <= 0) { maxval = 1; } } return ans; } // Driver code let arr = [ 0, -4, 0, -2 ]; let n = arr.length; document.write(findMaxProduct(arr, n)); // This code is contributed by souravghosh0416. </script> |
输出：
0
时间复杂性： O（n） 辅助空间： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
