Finding Maximum Product Sub-array in a Given Array in Java

Understanding Maximum Product Sub-array

This task involves finding the contiguous sub-array within a given array that has the maximum product.

We will explore three different methods to achieve this in Java.

Method 1: Using a Simple Iterative Approach

This method iterates through the array and keeps track of the maximum product.

public class MaxProductSubArray {
    public static int maxProductSubArray(int[] arr) {
        int maxProduct = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            int product = 1;
            for (int j = i; j < arr.length; j++) {
                product *= arr[j];
                maxProduct = Math.max(maxProduct, product);
            }
        }
        return maxProduct;
    }
    
    public static void main(String[] args) {
        int[] arr = {2, 3, -2, 4};
        System.out.println("Maximum Product Sub-array: " + maxProductSubArray(arr));
    }
}
            

Method 2: Using Dynamic Programming (Kadane's Algorithm Variant)

This method optimally finds the maximum product sub-array using dynamic programming.

public class MaxProductSubArrayDP {
    public static int maxProductSubArray(int[] arr) {
        int maxProduct = arr[0], minProduct = arr[0], result = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < 0) {
                int temp = maxProduct;
                maxProduct = minProduct;
                minProduct = temp;
            }
            maxProduct = Math.max(arr[i], maxProduct * arr[i]);
            minProduct = Math.min(arr[i], minProduct * arr[i]);
            result = Math.max(result, maxProduct);
        }
        return result;
    }
    
    public static void main(String[] args) {
        int[] arr = {2, 3, -2, 4};
        System.out.println("Maximum Product Sub-array: " + maxProductSubArray(arr));
    }
}
            

Method 3: Using Recursion

This method uses recursion to find the maximum product sub-array.

public class MaxProductSubArrayRec {
    public static int maxProductRec(int[] arr, int start, int end, int[] result) {
        if (start == end) return arr[start];
        int mid = (start + end) / 2;
        int leftMax = maxProductRec(arr, start, mid, result);
        int rightMax = maxProductRec(arr, mid + 1, end, result);
        result[0] = Math.max(result[0], Math.max(leftMax, rightMax));
        return result[0];
    }
    
    public static int maxProductSubArray(int[] arr) {
        int[] result = {Integer.MIN_VALUE};
        return maxProductRec(arr, 0, arr.length - 1, result);
    }
    
    public static void main(String[] args) {
        int[] arr = {2, 3, -2, 4};
        System.out.println("Maximum Product Sub-array: " + maxProductSubArray(arr));
    }
}