Maximum Product Subarray 

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.

Show Tags

Show Similar Problems

Attention: product means the result of multiplication, not the product item. (不是指商品的营业额，利润什么的)

dynamic programming O(n) in time and space. 

dpp[i] stores the biggest positive product containing nums[i]

dpn[i] stores the smallest negative product containing nums[i]

//Will the result exceeds the range of 32 bits integer?
//Product !!! 2 times 3, 2 * 3 the product is 6.
//What should I return if nums is empty?
//deal 0 carefully!

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int dpp[nums.size()];
        int dpn[nums.size()];
        int maxRe = nums[0];
        for(int i = 0; i < nums.size(); i++){
            int v = nums[i];
            if(i == 0){
                //init
                if(v < 0){
                    dpn[i] = v;
                    dpp[i] = 0;
                }
                else{
                    dpp[i] = v;
                    dpn[i] = 0;
                }
            }
            else{
                dpp[i] = max(v, max(v * dpp[i - 1], v * dpn[i  - 1]));
                dpn[i] = min(v, min(v * dpp[i - 1], v * dpn[i  - 1]));
                maxRe = max(dpp[i], maxRe);
            }
        }
        return maxRe;
    }
};

O(n) in time, O(1) in space solution.

Just simply replace dpp[i] with newDpp, replace dpp[i – 1] with oldDpp

replace dpn[i] with newDpn, replace dpn[i – 1] with oldDpn.

//Will the result exceeds the range of 32 bits integer?
//Product !!! 2 times 3, 2 * 3 the product is 6.
//What should I return if nums is empty?
//deal 0 carefully!

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int newDpp, oldDpp;
        int newDpn, oldDpn;
        int maxRe = nums[0];
        for(int i = 0; i < nums.size(); i++){
            int v = nums[i];
            if(i == 0){
                //init
                if(v < 0){
                    oldDpn = v;
                    oldDpp = 0;
                }
                else{
                    oldDpp = v;
                    oldDpn = 0;
                }
            }
            else{
                newDpp = max(v, max(v * oldDpp, v * oldDpn));
                newDpn = min(v, min(v * oldDpp, v * oldDpn));
                maxRe = max(newDpp, maxRe);
                oldDpn = newDpn;
                oldDpp = newDpp;
            }
        }
        return maxRe;
    }
};