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).