# Solution For Maximum Product Subarray

The Maximum Product Subarray problem is a classic problem in computer science. It can be solved using dynamic programming.

The problem statement is as follows:

Given an array of integers, find the contiguous subarray within it that has the largest product. For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product 6.

Solution:

We can solve this problem using dynamic programming. The key to solving this problem is recognizing that the maximum product subarray can be computed from the maximum product of the subarray ending at each position.

We will maintain two arrays:

1. `max_product[i]` stores the maximum product of the subarray ending at position i.
2. `min_product[i]` stores the minimum product of the subarray ending at position i.

We will then update these arrays at each position using the following equations:

1. `max_product[i] = max(nums[i], max_product[i-1] * nums[i], min_product[i-1] * nums[i])`
2. `min_product[i] = min(nums[i], max_product[i-1] * nums[i], min_product[i-1] * nums[i])`

The `max_product[i]` and `min_product[i]` represent the maximum and minimum product of subarrays ending at position `i`, respectively. If the current number `nums[i]` is positive, then the maximum and minimum product of subarrays ending at position `i` is either `nums[i]` itself or the maximum and minimum product of subarrays ending at position `i-1` times `nums[i]`. If `nums[i]` is negative, then the maximum and minimum product of subarrays ending at position `i` is either `nums[i]` itself or the minimum and maximum product of subarrays ending at position `i-1` times `nums[i]`.

Finally, we return the maximum value in `max_product`.

Here is the implementation of the solution in Python:

“`
def maxProduct(nums: List[int]) -> int:
max_product =  * len(nums)
min_product =  * len(nums)

``````max_product = nums
min_product = nums

for i in range(1, len(nums)):
if nums[i] >= 0:
max_product[i] = max(nums[i], max_product[i-1] * nums[i])
min_product[i] = min(nums[i], min_product[i-1] * nums[i])
else:
max_product[i] = max(nums[i], min_product[i-1] * nums[i])
min_product[i] = min(nums[i], max_product[i-1] * nums[i])

return max(max_product)
``````

“`

The time complexity of this solution is O(N), where N is the length of the input array. The space complexity is O(N), since we use two arrays to store the maximum and minimum product of subarrays ending at each position.

## Step by Step Implementation For Maximum Product Subarray

```class Solution {
public int maxProduct(int[] nums) {
// keep track of the maximum positive product seen so far
// and the minimum negative product seen so far
int maxPos = nums;
int minNeg = nums;
int maxSoFar = nums;

for (int i = 1; i < nums.length; i++) {
// update maximum positive product seen so far (if current num is positive)
if (nums[i] > 0) {
maxPos = Math.max(maxPos * nums[i], nums[i]);
// update minimum negative product seen so far (if current num is positive)
minNeg = Math.min(minNeg * nums[i], nums[i]);
}
// update maximum positive product seen so far (if current num is negative)
else if (nums[i] < 0) {
int temp = maxPos;
maxPos = Math.max(minNeg * nums[i], nums[i]);
// update minimum negative product seen so far (if current num is negative)
minNeg = Math.min(temp * nums[i], nums[i]);
}
// update result if necessary
maxSoFar = Math.max(maxPos, maxSoFar);
}
return maxSoFar;
}
}```
```class Solution:
def maxProduct(self, nums: List[int]) -> int:
# keep track of the maximum and minimum product so far
max_product = nums
min_product = nums
# also keep track of the overall maximum product
overall_max = nums

for i in range(1, len(nums)):
# update maximum and minimum product so far, given the current number
curr_max = max(max_product * nums[i], min_product * nums[i], nums[i])
curr_min = min(max_product * nums[i], min_product * nums[i], nums[i])

# update overall maximum
overall_max = max(overall_max, curr_max)

# update maximum and minimum product so far for next iteration
max_product = curr_max
min_product = curr_min

return overall_max```
```/**
* @param {number[]} nums
* @return {number}
*/

var maxProduct = function(nums) {
let maxSoFar = nums;
let minSoFar = nums;
let max = nums;

for(let i=1; iclass Solution {
public:
int maxProduct(vector& nums) {
int n = nums.size();
int max_so_far = nums;
int min_so_far = nums;
int res = nums;

for (int i = 1; i < n; i++)
{

if (nums[i] == 0)
{
max_so_far = 1;
min_so_far = 1;
continue;
}

int curr_max = max(max_so_far*nums[i],
min_so_far*nums[i]);
int curr_min = min(max_so_far*nums[i],
min_so_far*nums[i]);

max_so_far = curr_max;
min_so_far = curr_min;

res = max(res, max_so_far);
}
return res;
}
};public int MaxProduct(int[] nums)
{
// keep track of the maximum product seen so far
// and the minimum product seen so far
int maxSoFar = nums;
int minSoFar = nums;

// overall maximum product
int maxProduct = nums;

for (int i = 1; i < nums.Length; i++)
{
// update maximum and minimum products seen so far
int currMax = Math.Max(nums[i], Math.Max(maxSoFar * nums[i], minSoFar * nums[i]));
int currMin = Math.Min(nums[i], Math.Min(maxSoFar * nums[i], minSoFar * nums[i]));

// update overall maximum product
maxProduct = Math.Max(maxProduct, currMax);

// update maximum and minimum products seen so far for next iteration
maxSoFar = currMax;
minSoFar = currMin;
}

return maxProduct;
}```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]