Maximum Product Subarray

LeetCode 152 | Difficulty: Medium

Medium

Problem Description

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Note that the product of an array with a single element is the value of that element.

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.

Constraints:

- `1 <= nums.length <= 2 * 10^4`

- `-10 <= nums[i] <= 10`

- The product of any subarray of `nums` is **guaranteed** to fit in a **32-bit** integer.

Topics: Array, Dynamic Programming

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

---

Solutions

Solution 1: C# (Best: 104 ms)

Metric	Value
Runtime	104 ms
Memory	N/A
Date	2018-04-13

Solution

public class Solution {
    public int MaxProduct(int[] nums) {
        int max_so_far = nums[0];
    int max_ending_here = nums[0];
    int min_ending_here = nums[0];
    
    for (int i = 1; i < nums.Length; i++)
    {
        if(nums[i]<0)
        {
            var temp = max_ending_here;
            max_ending_here = min_ending_here;
            min_ending_here = temp;
        }
        max_ending_here = Math.Max(max_ending_here * nums[i], nums[i]);
        min_ending_here = Math.Min(min_ending_here * nums[i], nums[i]);
        max_so_far = Math.Max(max_ending_here,max_so_far);
    }
    return max_so_far;
    }
}

📜 1 more C# submission(s)

Submission (2022-01-26) — 153 ms, 37.2 MB

public class Solution {
    public int MaxProduct(int[] nums) {
        int max_so_far = nums[0];
    int max_ending_here = 1;
    int min_ending_here = 1;
    
    for (int i = 0; i < nums.Length; i++)
    {
        int temp1 = max_ending_here * nums[i];
        int temp2 = min_ending_here * nums[i];
        
        max_ending_here = Math.Max(temp2, Math.Max(temp1, nums[i]));
        min_ending_here = Math.Min(temp2, Math.Min(temp1, nums[i]));
        max_so_far = Math.Max(max_ending_here,max_so_far);
    }
    return max_so_far;
    }
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.