Maximum Product Subarray - Java Solution

1. Introduction

This blog post focuses on solving the "Maximum Product Subarray" problem, a common challenge in array manipulation and dynamic programming. The task is to find the contiguous subarray within an integer array that has the largest product. It's a problem that tests the ability to handle array substructures and optimize for maximum or minimum values.

Problem

Given an integer array nums, the objective is to find the subarray that yields the largest product and return this product. The solution must handle various cases, including negative numbers, which can affect the product significantly.

2. Solution Steps

1. Initialize two variables, maxProduct and minProduct, to hold the maximum and minimum product ending at the current element.

2. Iterate through the array, calculating the maximum and minimum product at each step.

3. Update maxProduct and minProduct considering the current element and the product up to the previous element.

4. Keep track of the overall maximum product seen so far.

5. Handle the case of negative numbers by swapping maxProduct and minProduct when a negative number is encountered.

6. Return the overall maximum product.

3. Code Program

public class MaximumProductSubarray {
    public static void main(String[] args) {
        int[] nums = {2, 3, -2, 4};
        System.out.println(maxProduct(nums)); // Test the function
    }

    // Function to find the maximum product subarray
    public static int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int maxProduct = nums[0], minProduct = nums[0], result = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // Swap max and min if the current element is negative
            if (nums[i] < 0) {
                int temp = maxProduct;
                maxProduct = minProduct;
                minProduct = temp;
            }

            // Update maxProduct and minProduct
            maxProduct = Math.max(nums[i], maxProduct * nums[i]);
            minProduct = Math.min(nums[i], minProduct * nums[i]);

            // Update the result
            result = Math.max(result, maxProduct);
        }

        return result;
    }
}

Output:

6

Explanation:

1. maxProduct: This function computes the maximum product of a subarray within the given integer array nums.

2. It initializes maxProduct and minProduct to the first element of the array and sets result to track the maximum product found.

3. As the function iterates through the array, it handles the possibility of negative numbers by swapping maxProduct and minProduct. This is because multiplying a negative number with the smallest product could result in the largest product.

4. The function then updates maxProduct and minProduct based on the current element, considering the product up to the previous element.

5. The overall maximum product (result) is updated at each step if the current maxProduct is larger.

6. The approach ensures efficient computation by maintaining the highest and lowest product at each step, accounting for the impact of negative numbers on the product.