 Explore Edit Edit

# Program to find the maximum product subarray in a given array | Faceprep

Published on 09 Mar 2020

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

For example, consider the given array

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

Output: 1800

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

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

## Algorithm to find the maximum product subarray in the given array

1. Input the array elements.
2. If arr > 0, max = arr[i] and initialize max_so_far = arr[i].
3. Repeat from i = 1 to end of the array.
4. Multiply max with the next array element if it is positive and update max = max_so_far.
5. Else,skip the array element and move to the next array element.
6. Return max_so_far.

Program to find the maximum product subarray in the given array is given below.

C
C++
Java
Python 3

Output
Input - Enter the size of an array : 5 Input the array elements : 1 -3 -10 60 0 Output - Maximum product : 1800

Time complexity: O(n)

Recommended Programs  