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

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

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.




Program to find the maximum product subarray in a given array


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.


@@coding::1@@


Time complexity: O(n)


Recommended Programs








Program to find the maximum product subarray in a given array



c