Solution: Maximum Product Subarray
Problem Statement
Given an integer array, find the contiguous subarray (at least one number in it) that has the maximum product. Return this maximum product.
Examples

 Input: [2,3,2,4]
 Expected Output: 6
 Justification: The subarray [2,3] has the maximum product of 6.

 Input: [2,0,1]
 Expected Output: 0
 Justification: The subarray [0] has the maximum product of 0.

 Input: [2,3,2,4]
 Expected Output: 48
 Justification: The subarray [2,3,2,4] has the maximum product of 48.
Solution

Initialization:
 Start by initializing two variables,
maxCurrent
andminCurrent
, to the first element of the array. These variables will keep track of the current maximum and minimum product, respectively.  Also, initialize a variable
maxProduct
to the first element of the array. This will store the maximum product found so far.
 Start by initializing two variables,

Iterate through the array:
 For each number in the array (starting from the second number), calculate the new
maxCurrent
by taking the maximum of the current number, the product ofmaxCurrent
and the current number, and the product ofminCurrent
and the current number.  Similarly, calculate the new
minCurrent
by taking the minimum of the current number, the product ofmaxCurrent
and the current number, and the product ofminCurrent
and the current number.  Update
maxProduct
by taking the maximum ofmaxProduct
andmaxCurrent
.
 For each number in the array (starting from the second number), calculate the new

Handle negative numbers:
 Since a negative number can turn a large negative product into a large positive product, we need to keep track of both the maximum and minimum product at each step.

Return the result:
 After iterating through the entire array,
maxProduct
will have the maximum product of any subarray.
 After iterating through the entire array,
Algorithm Walkthrough
Using the input [2,3,2,4]:
 Start with
maxCurrent = 2
,minCurrent = 2
, andmaxProduct = 2
.  For the next number, 3:
 New
maxCurrent
= max(3, 2 * 3) = 6  New
minCurrent
= min(3, 2 * 3) = 3  Update
maxProduct
= max(2, 6) = 6
 New
 For the next number, 2:
 New
maxCurrent
= max(2, 3*(2)) = 2  New
minCurrent
= min(2, 6*(2)) = 12 maxProduct
remains 6
 New
 For the last number, 4:
 New
maxCurrent
= max(4, 2*4) = 4  New
minCurrent
= min(4, 12*4) = 48 maxProduct
remains 6
 New
 The final answer is 6.
Code
Python3
Python3
. . .
You must run your code first
Complexity Analysis
 Time Complexity: O(n)  We iterate through the array only once.
 Space Complexity: O(1)  We use a constant amount of space regardless of the input size.