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: 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 to Solve

The key idea is to maintain two variables at each position:

1. max_so_far: The maximum product ending at the current position.
2. min_so_far: The minimum product ending at the current position. This is crucial because multiplying two negative numbers results in a positive number.

For each number nums[i], we consider three possibilities:

• nums[i] itself: This might be the maximum product ending at this position.
• nums[i] * max_so_far: Multiplying the current number with the previous maximum product.
• nums[i] * min_so_far: Multiplying the current number with the previous minimum product (important for handling negative numbers).

We update max_so_far and min_so_far accordingly and track the overall maximum product encountered so far.

Detailed Explanation

Let's trace the example nums = [2,3,-2,4]

| i | nums[i] | max_so_far | min_so_far | max_product_so_far | |-----|---------|-------------|-------------|----------------------| | 0 | 2 | 2 | 2 | 2 | | 1 | 3 | 6 | 6 | 6 | | 2 | -2 | -12 | -12 | 6 | //Note: min_so_far becomes -12, which is crucial for the next step. | 3 | 4 | -48 | 6 | 6 | // max_so_far becomes 24(4*-12) but we update it with 4*6 =24

The max_product_so_far keeps track of the largest product found so far. At each step, we update max_so_far and min_so_far to include the current number's effect.

C# Code

public class Solution {
    public int MaxProduct(int[] nums) {
        if (nums == null || nums.Length == 0) return 0;

        int max_so_far = nums[0];
        int min_so_far = nums[0];
        int max_product_so_far = nums[0];

        for (int i = 1; i < nums.Length; i++) {
            int temp_max = Math.Max(nums[i], Math.Max(nums[i] * max_so_far, nums[i] * min_so_far));
            min_so_far = Math.Min(nums[i], Math.Min(nums[i] * max_so_far, nums[i] * min_so_far));
            max_so_far = temp_max;
            max_product_so_far = Math.Max(max_product_so_far, max_so_far);
        }

        return max_product_so_far;
    }
}

Complexity Analysis

• 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 a constant number of variables to store the maximum and minimum products.