# [leetcode] Maximum Product Subarray

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

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;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.