Find max product contiguous subarray

Brute Force Solution:

The brute force solution involves iterating through all possible subarrays of the given array and computing their product. The subarray with the maximum product is the answer. Here's the code:

public static int maxProductSubarray(int[] nums) {
    int n = nums.length;
    int maxProduct = Integer.MIN_VALUE;

    for (int i = 0; i < n; i++) {
        int product = 1;
        for (int j = i; j < n; j++) {
            product *= nums[j];
            maxProduct = Math.max(maxProduct, product);
        }
    }

    return maxProduct;
}

Time Complexity: O(n^2) where n is the length of the input array. This is because we need to iterate through all possible subarrays, and there are n^2 such subarrays.

Space Complexity: O(1) since we are not using any extra space other than a few variables to keep track of the maximum product and current product.

Optimal Solution:

To find the maximum product contiguous subarray, you can use a modification of the Kadane's algorithm for finding the maximum sum contiguous subarray. The idea is to keep track of both the maximum product and minimum product that can be obtained up to the current index, because multiplying a negative number with a minimum product can lead to a maximum product. Here's the Java code:

public class MaxProductContiguousSubarray {
    public static void main(String[] args) {
        int[] arr = {2, 3, -2, 4, -1, 0, 5, -2, -1};
        int[] maxSubarray = findMaxProductContiguousSubarray(arr);
        System.out.print("Maximum product contiguous subarray: ");
        for (int i = 0; i < maxSubarray.length; i++) {
            System.out.print(maxSubarray[i] + " ");
        }
    }

    public static int[] findMaxProductContiguousSubarray(int[] arr) {
        int n = arr.length;
        int maxProduct = 1, minProduct = 1, maxEndingHere = 1, minEndingHere = 1, startIndex = 0, endIndex = 0, s = 0;

        for (int i = 0; i < n; i++) {
            if (arr[i] > 0) {
                maxEndingHere = maxEndingHere * arr[i];
                minEndingHere = Math.min(minEndingHere * arr[i], 1);
            } else if (arr[i] == 0) {
                maxEndingHere = 1;
                minEndingHere = 1;
                s = i + 1;
            } else {
                int temp = maxEndingHere;
                maxEndingHere = Math.max(minEndingHere * arr[i], 1);
                minEndingHere = temp * arr[i];
            }

            // update result 
            if (maxEndingHere > maxProduct) {
                maxProduct = maxEndingHere;
                startIndex = s;
                endIndex = i;
            }
        }

        int[] subarray = new int[endIndex - startIndex + 1];
        for (int i = 0; i < subarray.length; i++) {
            subarray[i] = arr[startIndex + i];
        }
        return subarray;
    }
}

Time Complexity: O(n) where n is the length of the input array. This is because we only need to iterate through the input array once.

Space Complexity: O(1) since we are not using any extra space other than a few variables to keep track of the maximum product, minimum product, and result.