给定一个包含正整数和负整数的数组，求最大乘积子数组的乘积。预期的时间复杂度为O（n），并且只能使用O（1）个额外空间。
null
例如：
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}
天真的解决方案：
其思想是遍历每个相邻的子阵列，找到每个子阵列的乘积，并从这些结果中返回最大乘积。
以下是上述方法的实施情况。
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 yashbeersingh42 |
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 yashbeersingh42 |
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> |
输出：
Maximum Sub array product is 112
时间复杂性： O（N） 2. ) 辅助空间： O（1）
高效的解决方案：
下面的解决方案假设给定的输入数组总是有正输出。该解决方案适用于上述所有情况。它不适用于像{0,0，-20,0}，{0,0,0}这样的数组。。解决方案可以很容易地修改以处理这种情况。 类似于 最大和邻接子阵 问题这里唯一需要注意的是，最大乘积也可以通过以前一个元素结尾的最小（负）乘积乘以该元素得到。例如，在数组{12,2，-3，-5，-6，-2}中，当我们在元素-2处时，最大乘积是的乘积，最小乘积以-6和-2结尾。
笔记 ：如果数组的所有元素都是负数，则上述算法的最大乘积为1。所以，如果最大乘积是1，那么我们必须返回数组的最大元素。
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> |
输出
Maximum Sub array product is 112
时间复杂性： O（n） 辅助空间： O（1）
高效的解决方案：
上面的解决方案假设给定数组总是有一个正结果，而在数组只包含{0,0，-20,0}，{0,0,0}等非正元素的情况下，该结果不起作用。。修正后的解也类似于使用Kadane算法的最大和邻接子阵问题。为了便于理解，我们没有像之前的解决方案那样使用任何标志。这里我们使用3个变量 max_到目前为止，max_在这里结束，min_在这里结束 .对于每个索引，以该索引结尾的最大数字为 最大值（arr[i]、max_ending_here*arr[i]、min_ending_here[i]*arr[i]） .同样，以此处结尾的最小数字将是这3个数字中的最小值。因此，我们得到了最大乘积子阵的最终值。
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 is code is contributed by kaustav |
本文由 德拉杰·贾因 并由Geeksforgeks团队审核。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
