> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/duo-zhuang-tai-dp/maximum-product-subarray.md).

# Maximum Product Subarray

<https://leetcode.com/problems/maximum-product-subarray/description/>

> Find the contiguous subarray within an array (containing at least one number) which has the largest product.
>
> For example, given the array \[2,3,-2,4],
>
> the contiguous subarray \[2,3] has the largest product = 6.

## Thoughts

求子数组某性质最优值用DP。让f\[i]表示以nums\[i]为尾的子数组最大积，容易想到f\[i] = max(nums\[i], f\[i-1] \* nums\[i])。 但这个状态转移方程是有问题的。比如\[-1,2,-3], f\[0] = -1, f\[1] = 2, f\[2] = -3，但f\[2]实际应该等于6，最长子数组就是nums. 我们再观察f\[2]得到的最大值是i之前的负数和当前负数相乘得到的，也就是说当当前为负数时，让它乘以一个越小的数，我们得到的最大值越大。因此我们可以再定义一个g\[i]，存储以nums\[i]为尾的子数组最小积。

## Code

```
/*
 * @lc app=leetcode id=152 lang=cpp
 *
 * [152] Maximum Product Subarray
 */
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        const int N = nums.size();
        if (N == 0) return 0;
        int mi = nums[0], mx = nums[0], res = nums[0];
        for (int i = 1; i < N; ++i) {
            const int num = nums[i], mi_i = mi * num, mx_i = mx * num;
            int f = max(num, max(mi_i, mx_i));
            res = max(res, f);
            mi = min(num, min(mi_i, mx_i));
            mx = f;
        }
        return res;
    }
};


```

## Analysis

做题耗时40min

时间复杂度O(n).