Java program for finding the maximum product of sub-array of a given array

Maximum product of sub-array

Program to find the maximum product 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

java program to find maximum-product-of-sub-array

Algorithm

  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.

 

import java.util.*;

 class PrepInsta

{
    static int min (int m1, int n) 
{
return m < n? m : n;
}

static int max (int m, int n)
{
return m > n? x : n; } static int SubarrayProduct(int arr[], int n) { int max_ending_here = 1; int min_ending_here = 1; int max_so_far = 1; for (int i = 0; i < n; i++)
{
if (arr[i] > 0) { max_ending_here = max_ending_here*arr[i]; min_ending_here = min (min_ending_here * arr[i], 1); } else if (arr[i] == 0) { max_ending_here = 1; min_ending_here = 1; } else { int temp = max_ending_here; max_ending_here = max (min_ending_here * arr[i], 1); min_ending_here = temp * arr[i]; } if (max_so_far < max_ending_here) max_so_far = max_ending_here; } return max_so_far; } public static void main(String[] args) { int[] arr = new int[]{-1, -3, -10, 60,0}; int siz = arr.l; System.out.print( "Maximum product subarray : "); System.out.print(maxSubarrayProduct(arr, size)); } }
output
1800