Maximum Product Subarray Leetcode Solution Java Program

Finding a contiguous subarray within a given array that yields the largest product is a common challenge in computer science, requiring careful consideration of positive, negative, and zero values. In this article, you will learn how to approach the Maximum Product Subarray problem and implement efficient Java solutions.

Problem Statement

The Maximum Product Subarray problem asks us to find the contiguous subarray within an integer array that has the largest product. A contiguous subarray means elements must be adjacent in the original array. This problem differs from "maximum sum subarray" because negative numbers, when multiplied, can become positive and potentially very large, which adds complexity.

For instance, given the array nums = [2, 3, -2, 4], the subarray [2, 3] has a product of 6. The subarray [2, 3, -2, 4] has a product of -48. However, the subarray [4] has a product of 4. The maximum product subarray here is [2, 3], yielding 6. Consider nums = [-2, 0, -1]. The maximum product is 0 (from [0]), not -1 (from [-1]) or 2 (from [-2,-1], which is not a contiguous subarray including 0).

Example

Let's consider the array nums = [2, 3, -2, 4]. Using a straightforward (brute force) approach, if we iterate through all possible subarrays and calculate their products, the output for this specific input would eventually lead to 6.

Background & Knowledge Prerequisites

To understand and implement the solutions effectively, readers should have a basic grasp of:

• Java Syntax: Variables, data types, conditional statements (if-else), loops (for).
• Arrays: How to declare, initialize, and access elements in one-dimensional arrays.
• Basic Arithmetic Operations: Multiplication and understanding how negative numbers affect products.
• Math.max() and Math.min(): For finding the maximum or minimum of two or more values.

Use Cases or Case Studies

This problem, and similar array manipulation techniques, find applications in various domains:

• Financial Analysis: Identifying periods of maximum growth (product of daily percentage changes) in stock prices or investment returns.
• Signal Processing: Detecting segments in a signal where the cumulative product of intensity values is maximized, indicating a strong or significant event.
• Bioinformatics: Analyzing sequences (e.g., DNA or protein sequences) to find segments with the highest "score" based on a product-based scoring matrix.
• Image Processing: Locating regions in an image that exhibit the highest product of pixel intensity values, useful for feature detection or anomaly identification.
• Data Compression: Algorithms that rely on products for encoding or decoding data streams might use similar logic to optimize segment processing.

Solution Approaches

We will explore two distinct approaches to solve the Maximum Product Subarray problem: a brute-force method for clarity, and an optimized dynamic programming approach for efficiency.

Approach 1: Brute Force (O(n^2) Time Complexity)

This approach involves iterating through all possible contiguous subarrays, calculating the product for each, and keeping track of the overall maximum product found.

• Summary: Nested loops are used to define all possible start and end points of subarrays. For each subarray, its product is calculated and compared with the current maximum.

// Maximum Product Subarray - Brute Force
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums1 = {2, 3, -2, 4};
        System.out.println("Array: " + Arrays.toString(nums1) + ", Max Product: " + maxProductBruteForce(nums1)); // Expected: 6

        int[] nums2 = {-2, 0, -1};
        System.out.println("Array: " + Arrays.toString(nums2) + ", Max Product: " + maxProductBruteForce(nums2)); // Expected: 0

        int[] nums3 = {-2, -3, -1};
        System.out.println("Array: " + Arrays.toString(nums3) + ", Max Product: " + maxProductBruteForce(nums3)); // Expected: 6
    }

    public static int maxProductBruteForce(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0; // Or throw IllegalArgumentException
        }

        int maxProduct = nums[0]; // Initialize with the first element

        // Outer loop for the starting index of the subarray
        for (int i = 0; i < nums.length; i++) {
            int currentProduct = 1; // Product for the current subarray starting at i
            // Inner loop for the ending index of the subarray
            for (int j = i; j < nums.length; j++) {
                currentProduct *= nums[j]; // Multiply by the next element
                maxProduct = Math.max(maxProduct, currentProduct); // Update global max product
            }
        }
        return maxProduct;
    }
}

Run

• Sample Output:

Array: [2, 3, -2, 4], Max Product: 6
Array: [-2, 0, -1], Max Product: 0
Array: [-2, -3, -1], Max Product: 6

• Stepwise Explanation:

1. Initialize maxProduct with the first element of the array. This handles cases with single elements or arrays where all products are negative, ensuring we return the largest single element.
2. Use an outer loop with index i to iterate through each possible starting position of a subarray.
3. Inside the outer loop, initialize currentProduct to 1 for each new starting position i.
4. Use an inner loop with index j starting from i to extend the current subarray.
5. In the inner loop, multiply currentProduct by nums[j]. This progressively calculates the product of the subarray nums[i...j].
6. After each multiplication, update maxProduct by comparing it with currentProduct using Math.max().
7. After checking all possible subarrays, return maxProduct.

Approach 2: Optimized Dynamic Programming (O(n) Time Complexity)

This is the most efficient approach, solving the problem in a single pass. The key insight is that because negative numbers can turn a small product into a large one (e.g., -10 * -5 = 50), we need to keep track of both the maximum and minimum products ending at the current position.

• Summary: Iterates through the array once, maintaining two variables: max_so_far (maximum product ending at the current position) and min_so_far (minimum product ending at the current position). These are updated based on the current number, and a global maximum result is maintained.

// Maximum Product Subarray - Optimized
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums1 = {2, 3, -2, 4};
        System.out.println("Array: " + Arrays.toString(nums1) + ", Max Product: " + maxProductOptimized(nums1)); // Expected: 6

        int[] nums2 = {-2, 0, -1};
        System.out.println("Array: " + Arrays.toString(nums2) + ", Max Product: " + maxProductOptimized(nums2)); // Expected: 0

        int[] nums3 = {-2, -3, -1};
        System.out.println("Array: " + Arrays.toString(nums3) + ", Max Product: " + maxProductOptimized(nums3)); // Expected: 6

        int[] nums4 = {0, 2};
        System.out.println("Array: " + Arrays.toString(nums4) + ", Max Product: " + maxProductOptimized(nums4)); // Expected: 2

        int[] nums5 = {-1, -2, -9, -6};
        System.out.println("Array: " + Arrays.toString(nums5) + ", Max Product: " + maxProductOptimized(nums5)); // Expected: 108
    }

    public static int maxProductOptimized(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0; // Or throw IllegalArgumentException
        }

        int max_so_far = nums[0]; // Maximum product ending at current position
        int min_so_far = nums[0]; // Minimum product ending at current position
        int result = nums[0];     // Global maximum product found so far

        // Iterate from the second element
        for (int i = 1; i < nums.length; i++) {
            int currentNum = nums[i];

            // If current number is negative, swap max_so_far and min_so_far
            // because multiplying by a negative number reverses their roles
            if (currentNum < 0) {
                int temp = max_so_far;
                max_so_far = min_so_far;
                min_so_far = temp;
            }

            // Update max_so_far: it's either the current number itself,
            // or the product of current number and previous max_so_far
            max_so_far = Math.max(currentNum, max_so_far * currentNum);

            // Update min_so_far: it's either the current number itself,
            // or the product of current number and previous min_so_far
            min_so_far = Math.min(currentNum, min_so_far * currentNum);

            // Update the global result
            result = Math.max(result, max_so_far);
        }
        return result;
    }
}

Run

• Sample Output:

Array: [2, 3, -2, 4], Max Product: 6
Array: [-2, 0, -1], Max Product: 0
Array: [-2, -3, -1], Max Product: 6
Array: [0, 2], Max Product: 2
Array: [-1, -2, -9, -6], Max Product: 108

• Stepwise Explanation:

1. Initialize max_so_far, min_so_far, and result all to nums[0]. max_so_far tracks the maximum product ending at the current index, min_so_far tracks the minimum product ending at the current index, and result stores the overall maximum product found.
2. Iterate through the array starting from the second element (i = 1).
3. For each currentNum:

• Handle Negatives: If currentNum is negative, it means that multiplying max_so_far by currentNum will yield a smaller (more negative) number, and multiplying min_so_far by currentNum will yield a larger (less negative or positive) number. Therefore, swap max_so_far and min_so_far to prepare for the subsequent multiplications.
• Update max_so_far: The new maximum product ending at i is the larger of currentNum itself (starting a new subarray) or the product of max_so_far (from i-1) and currentNum.
• Update min_so_far: Similarly, the new minimum product ending at i is the smaller of currentNum itself or the product of min_so_far (from i-1) and currentNum.
• Update result: The overall result is updated by comparing it with the current max_so_far.

1. After iterating through the entire array, result will hold the maximum product of any contiguous subarray.

Conclusion

The Maximum Product Subarray problem highlights the nuances of working with products in arrays, particularly the transformative effect of negative numbers. While a brute-force approach offers a straightforward understanding, its quadratic time complexity makes it impractical for large datasets. The optimized dynamic programming solution efficiently addresses this by tracking both maximum and minimum products ending at each position, achieving a linear time complexity (O(n)), which is crucial for performance.

Summary

• The Maximum Product Subarray problem seeks the contiguous subarray with the largest product.
• Challenges arise from negative numbers, where multiplying two negatives yields a positive, potentially large product, and zeros, which reset products.
• The brute-force approach involves checking all O(n^2) subarrays, leading to an O(n^2) time complexity.
• The optimal solution utilizes dynamic programming, tracking max_so_far and min_so_far products ending at the current position.
• This optimized approach handles negative numbers by swapping max_so_far and min_so_far when a negative number is encountered, ensuring correct updates.
• The O(n) dynamic programming approach is the preferred method for its efficiency.