*856*

In the given problem statement, we have an array of integers and we need to find the maximum product possible for a contiguous subarray.

The most important part of this problem is that the elements have to be contiguous. So special attention needs to be given for negative numbers and zeroes.

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

Input:nums = [ 2 , 3 , -2 , -5 , 6 , -1 , 4 ]Output:360Explanation:[ 2 , 3 , -2 , -5 , 6 ] has the largest product 360.

#### Brute Force Solution

The brute force approach to finding the maximum product subarray involves checking all possible subarrays and calculating their products to find the maximum product.

- Initialize a variable
`max_product`

to store the maximum product, initially set to the minimum possible value. - Iterate through all possible starting indices of the subarray.
- For each starting index, iterate through all possible ending indices greater than or equal to the starting index.
- Extract the subarray from the starting index to the ending index.
- Calculate the product of all elements in the subarray.
- Update
`max_product`

if the calculated product is greater than the current maximum. - Repeat steps 3-6 until all possible subarrays are considered.
- Return
`max_product`

as the maximum product of a subarray within the given array.

This brute force approach has a time complexity of O(n^3), where n is the length of the input array. Since it involves nested loops, it checks every possible subarray combination, making it highly inefficient for large input sizes.

While the brute force solution is straightforward, it is not efficient for solving larger instances of the problem. We need something better.

#### Efficient Solution

To solve this problem, you can utilize the dynamic programming approach. Here’s a general outline of the solution:

- Initialize two variables,
`max_product`

and`min_product`

, both set to the first element of the array. - Initialize a variable
`max_global`

to store the overall maximum product. - Iterate through the array starting from the second element.
- For each element, update
`max_product`

and`min_product`

by considering three possibilities: a. Multiply the current element by`max_product`

(to include the current element in the positive product chain). b. Multiply the current element by`min_product`

(to include the current element in the negative product chain, in case the current element is negative). c. Start a new subarray from the current element (if the previous subarray’s product is not significant). - Update
`max_global`

by comparing it with`max_product`

. - Repeat steps 4-5 until all elements are processed.
- Return
`max_global`

as the maximum product of a subarray within the given array.

This approach allows you to keep track of both the maximum and minimum product at each step, considering the possibility of negative numbers and the potential of changing the product’s sign.

#### Code

```
int maxProduct(int[] nums) {
int n = nums.length;
int leftProduct = 1;
int rightProduct = 1;
int ans = nums[0];
for (int i = 0; i < n; i++) {
//if any of leftProduct or rightProduct become 0 then update it to 1
leftProduct = leftProduct == 0 ? 1 : leftProduct;
rightProduct = rightProduct == 0 ? 1 : rightProduct;
//prefix product
leftProduct *= nums[i];
//suffix product
rightProduct *= nums[n - 1 - i];
ans = Math.max(ans, Math.max(leftProduct, rightProduct));
}
return ans;
}
```

Code language: Java (java)

*Time Complexity:* O(n)*Space Complexity:* O(n)