Maximum Product Subarray medium

Problem Statement

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1

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

Example 2

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

Steps

1. Initialization: We need to keep track of the maximum and minimum product ending at the current position. We initialize both max_so_far and min_so_far to the first element of the array. We also initialize max_product to the first element, representing the maximum product encountered so far.

2. Iteration: Iterate through the array starting from the second element. For each element num:

   • Calculate the potential maximum and minimum products including the current element:
     • temp_max = max(num, max_so_far * num, min_so_far * num)
     • temp_min = min(num, max_so_far * num, min_so_far * num)
   • Update max_so_far and min_so_far:
     • max_so_far = temp_max
     • min_so_far = temp_min
   • Update max_product:
     • max_product = max(max_product, max_so_far)

3. Return: After iterating through the entire array, max_product holds the maximum product of a contiguous subarray.

Explanation

The key insight is that the maximum product at a given position can come from three possibilities:

1. The current element itself.
2. The product of the current element and the maximum product ending at the previous position.
3. The product of the current element and the minimum product ending at the previous position (this handles cases with negative numbers where multiplying a negative minimum with a negative current element can result in a large positive product).

We need to track both the maximum and minimum products to handle these cases efficiently. The temp_max and temp_min variables ensure we correctly determine the maximum and minimum products at each step, considering all three possibilities.

Code

class Solution {
    public int maxProduct(int[] nums) {
        int max_so_far = nums[0];
        int min_so_far = nums[0];
        int max_product = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            int temp_max = Math.max(num, Math.max(max_so_far * num, min_so_far * num));
            int temp_min = Math.min(num, Math.min(max_so_far * num, min_so_far * num));
            max_so_far = temp_max;
            min_so_far = temp_min;
            max_product = Math.max(max_product, max_so_far);
        }
        return max_product;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1). We use only a few constant extra variables.