152. Maximum Product Subarray

• Difficulty: Medium

• Topics: Array, Dynamic Programming

• Similar Questions:

  • Maximum Subarray

  • House Robber

  • Product of Array Except Self

  • Maximum Product of Three Numbers

  • Subarray Product Less Than K

Problem:

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Solutions:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;

        vector<int> maxValue (n, 0);
        vector<int> minValue (n, 0);

        maxValue[0] = nums[0];
        minValue[0] = nums[0];

        for (int i = 1; i < nums.size(); ++i) {
            maxValue[i] = max(nums[i], max(minValue[i-1] * nums[i], maxValue[i-1] * nums[i]));
            minValue[i] = min(nums[i], min(minValue[i-1] * nums[i], maxValue[i-1] * nums[i]));
        }

        int ret = maxValue[0];
        for (int i = 1; i < nums.size(); ++i) {
            ret = max(ret, maxValue[i]);
        }

        return ret;
    }
};