Maximum product subarray

Given an integer array nums, find a subarray that has the largest product, and return the product. A subarray of an array is a contiguous sequence of elements within that array.

Example

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Approach

1. Initialize variables maxEndingHere, minEndingHere, and maxProductSoFar.
2. Iterate through the array from left to right, calculating maxEndingHere and minEndingHere for each element.
3. Update maxProductSoFar by taking the maximum of the current maxProductSoFar and maxEndingHere.
4. Continue the loop until all elements are processed.
5. After the loop, maxProductSoFar will contain the maximum product of a subarray in the integer array.

Complexity

• Time Complexity: O(n), where 'n' is the length of the input array.
• Space Complexity: O(1),  because the code uses a fixed number of variables.

Code

## Java Code

public class MaximumProductSubarray {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        if (n == 0)
            return 0;

        int maxEndingHere = nums[0];
        int minEndingHere = nums[0];
        int maxProductSoFar = nums[0];

        for (int i = 1; i < n; i++) {
            int tempMax = maxEndingHere;
            maxEndingHere = Math.max(nums[i], Math.max(nums[i] * maxEndingHere, nums[i] * minEndingHere));
            minEndingHere = Math.min(nums[i], Math.min(nums[i] * tempMax, nums[i] * minEndingHere));
            maxProductSoFar = Math.max(maxProductSoFar, maxEndingHere);
        }

        return maxProductSoFar;
    }

    public static void main(String[] args) {
        MaximumProductSubarray solution = new MaximumProductSubarray();
        int[] nums = { 2, 3, -2, 4 };
        int result = solution.maxProduct(nums);
        System.out.println("Maximum subarray product: " + result);
    }
}

Output

Maximum subarray product: 6