Maximum Product Subarray medium

Problem Statement

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: The subarray [2,3] has the largest product 6.

Example 2

Input: nums = [-2,0,-1] Output: 0 Explanation: The subarray [0] has the largest product 0.

Steps and Explanation

The key to solving this problem efficiently is to understand that the maximum product at a given index can come from three sources:

1. The number itself: This is the simplest case.
2. The maximum product ending at the previous index, multiplied by the current number: This extends a positive product sequence.
3. The minimum product ending at the previous index, multiplied by the current number: This handles cases where a negative number turns a previously negative product into a positive one (e.g., -2 * -3 = 6).

We need to track both the maximum and minimum products ending at each index because of the possibility of negative numbers. We'll use two variables to track these: max_so_far and min_so_far.

Algorithm:

1. Initialization: Initialize max_so_far and min_so_far to the first element of the array. Also initialize max_product to the first element (this will store the overall maximum product).
2. Iteration: Iterate through the array starting from the second element.
3. For each element:
   • Calculate three potential maximum products:
     • current_num: The current number itself.
     • max_so_far * current_num: Extending the maximum positive product.
     • min_so_far * current_num: Extending the minimum negative product (potentially becoming positive).
   • Update max_so_far to be the maximum of these three.
   • Update min_so_far to be the minimum of these three.
   • Update max_product if the current max_so_far is greater than max_product.
4. Return: Return max_product.

Code (Typescript)

function maxProduct(nums: number[]): number {
    let max_so_far = nums[0];
    let min_so_far = nums[0];
    let max_product = nums[0];

    for (let i = 1; i < nums.length; i++) {
        let current_num = nums[i];
        let temp_max = Math.max(current_num, max_so_far * current_num, min_so_far * current_num);
        let temp_min = Math.min(current_num, max_so_far * current_num, min_so_far * current_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.

This solution provides an efficient way to find the maximum product subarray, handling both positive and negative numbers effectively. The use of temp_max and temp_min ensures that the updates to max_so_far and min_so_far are done correctly without overwriting values prematurely.