Find maximum product sub-array in a given array

Maximum product of sub-array

Program to find the maximum product of sub array in a given array is discussed here. Given an array of integers as input, the task is to find the sub array from the given input array whose product is maximum.

Example

Input: {-1, -3, -10, 60,0}

Output: 1800

Sub-array : {-3, -10, 60}

Product of the sub-array = -3 * -10 * 60 = 1800

maximum product of subarray

 

Algorithm

  • Input the array elements.
  • Initialize a variable result
  • Iterate from i=0 till i=(length of array)
  • Initialize a variable product, which will have value 1 for each value of i
  • Iterate from j=i till j=(length of array)
  • For each value of j compare max(product,result) and store in result
  • For each value of j, product=product*arr[j]
  • After the end of iteration of j   again compare max(product,result) and store in result
  • After the iteration of i, print result

 

Python Code

print("Input length of array")
n=int(input())
arr=[]
print("Enter elements of array")
for i in range(n):
arr.append(int(input()))
result=1
for i in range(n):
product=1
for j in range(i,n):
result=max(result,product)
product=product*arr[j]
result=max(product,result)
print("Maximum product of subarray is ",result)
Input length of array
5
Enter elements of array
-1
-3
-10
60
0
Maximum product of subarray is 1800