Explore
ProGrad Programs
About Us

Edit
Reply




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] > 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







If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in