# Find maximum product sub-array in a given array

## Maximum product of sub-array in Python

Here, in this page we will discuss the program to find the maximum product of sub-array in python programming language. We are given with an array and need to return the maximum value of the product of the sub-array.

## Method Discussed

• Method 1 : Brute Force solution
• Method 2 : Efficient solution

Let’s discuss above two methods in brief.

## Method 1 :

• Create a variable say result, set result = arr[0], this variable hold the required maximum product.
• Run a loop for range(n)
• Create a variable mul = arr[i], this variable hold the product of sub-array.
• Run a inner loop, set result = max(result, mul)
• And, mul *= arr[j]
• Update, result = max(result, mul)
• Return result.

### Time and Space Complexity :

• Time Complexity : O(n2)
• Space Complexity : O(1)

### Method 1 : Code in Python

Run
```def maxSubarrayProduct(arr, n):

# Initializing result
result = arr[0]

for i in range(n):

mul = arr[i]

# traversing in current subarray
for j in range(i + 1, n):
result = max(result, mul)
mul *= arr[j]

# updating the result for (n-1)th index.
result = max(result, mul)

return result

arr = [ 1, -2, -3, 0, 7, -8, -2 ]
n = len(arr)
print("Maximum sub-array product is" , maxSubarrayProduct(arr, n))```

### Output

`Maximum sub-array product is 112`

## Method 2 :

This is the efficient solution and is also similar to Largest Sum Contiguous Subarray problem which uses Kadane’s algorithm.

• Declare three variables say max_so_far, max_ending_here & min_ending_here.
• For every index the maximum number ending at that index will be the maximum(arr[i], max_ending_here * arr[i], min_ending_here[i]*arr[i]).
• Similarly the minimum number ending here will be the minimum of these 3.
• Thus we get the final value for maximum product subarray.

### Time and Space Complexity :

• Time Complexity : O(n)
• Space Complexity : O(1)

### Method 2 : Code in Python

```def maxSubarrayProduct(arr, n):
max_ending_here = arr[0];
min_ending_here = arr[0];
max_so_far = arr[0];

for i in range(n):
temp = max({arr[i], arr[i] * max_ending_here, arr[i] * min_ending_here});
min_ending_here = min({arr[i], arr[i] * max_ending_here, arr[i] * min_ending_here});
max_ending_here = temp
max_so_far = max(max_so_far, max_ending_here)
return max_so_far

arr = [ 1, -2, -3, 0, 7, -8, -2 ]
n = len(arr)
print("Maximum sub-array product is" , maxSubarrayProduct(arr, n))```

### Output

`Maximum sub-array product is 112`

### One comment on “Find maximum product sub-array in a given array”

• Prashant

arr=list(map(int,input().split()))
sum=1
for i in range(len(arr)):
if arr[i]==0:
pass
else:sum*=arr[i]
print(abs(sum))