Article From:https://www.cnblogs.com/yaoyudadudu/p/9219389.html

Description of the 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.

 

The idea of solving the problem:

First of all, we will consider the way of tired multiplication.

However, because there are negative numbers in the array, the current negative value on the smallest value may be the maximum.

So we can use two arrays to store the minimum and maximum values respectively.

When updating the most array, you need to compare it with nums[i].

 mx[i] = max(max(prod1, prod2), nums[i]);
 mn[i] = min(min(prod1, prod2), nums[i]);

 

Code:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        if(nums.size() == 1)
            return nums[0];
        vector<int> mx(nums.size());
        vector<int> mn(nums.size());
        mx[0] = nums[0];
        mn[0] = nums[0];
        int ret = mx[0];
        for(int i = 1; i < nums.size(); i++){
            int prod1 = mx[i-1]*nums[i];
            int prod2 = mn[i-1]*nums[i];
            mx[i] = max(max(prod1, prod2), nums[i]);
            mn[i] = min(min(prod1, prod2), nums[i]);
            ret = max(mx[i], ret);
        }
        return ret;
    }
};

 

Link of this Article: 152. Maximum Product Subarray

Leave a Reply

Your email address will not be published. Required fields are marked *