In this tutorial we will learn how to get the Maximum Product Subarray In Java. This is a Data Structure Problem which asked in many interviews.
Problem?
You have an array, find the subarray which elements have the maximum product or the multiplication in Java. Recursion is the best way to solving the Data Structure problem.
import java.io.*;
class Maxproduct{
// rogram to find Maximum Product Subarray
// Returns the product value
// of max product subarray.
static int maxSubarrayProduct(int arr[], int n)
{
// max positive product
// ending at the current position
int max_ending_here = arr[0];
// min negative product ending
// at the current position
int min_ending_here = arr[0];
// Initialize overall max product
int max_so_far = arr[0];
// /* Traverse through the array.
// the maximum product subarray ending at an index
// will be the maximum of the element itself,
// */
for (int i = 1; i < n; i++) {
int temp = Math.max(
Math.max(arr[i], arr[i] * max_ending_here),
arr[i] * min_ending_here);
min_ending_here = Math.min(
Math.min(arr[i], arr[i] * max_ending_here),
arr[i] * min_ending_here);
max_ending_here = temp;
max_so_far
= Math.max(max_so_far, max_ending_here);
}
return max_so_far;
}
// Driver code
public static void main(String args[])
{
int[] arr = { 1, 2, -3, 10, 7, -8, -2, 4, 2 };
int n = arr.length;
System.out.printf("Maximum product Sub array %d",
maxSubarrayProduct(arr, n));
}
}
Thank for visiting this tutorial. You can comment in the comments section below for any query or doubt. You can learn more about it from here.
