最大产品子数组 · GeeksForGeeks 中文系列教程

# 最大产品子数组 > 原文： [https://www.geeksforgeeks.org/maximum-product-subarray/](https://www.geeksforgeeks.org/maximum-product-subarray/) 给定一个同时包含正整数和负整数的数组，请找到最大乘积子数组的乘积。预期的时间复杂度为`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[] = {-2, -3, 0, -2, -40} Output: 80 // The subarray is {-2, -40} ``` 以下解决方案假定给定的输入数组始终具有正输出。该解决方案适用于上述所有情况。它不适用于`{0, 0, -20, 0}`，`{0, 0, 0}`等数组。等等。可以轻松修改解决方案以处理这种情况。与[最大和连续子数组](https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/)问题相似。这里唯一需要注意的是，最大乘积也可以通过以前一个元素乘以该元素结尾的最小（负）乘积来获得。例如，在数组`{12, 2, -3, -5, -6, -2}`中，当我们在元素 -2 处时，最大乘积是的乘积，最小乘积以 -6 和 -2 结尾。 ## C++ ```cpp // 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[0]); cout << "Maximum Sub array product is " << maxSubarrayProduct(arr, n); return 0; } // This is code is contributed by rathbhupendra ```