# 最大產品子數組 > 原文： [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 ```