Maximum Product Subarray

Dynamic Programming

25 min

Problem Statement

Given an integer array nums, find a contiguous non-empty subarray within the array 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.

Example

Example 1:

Input: nums = [2,3,-2,4]

nums: [2, 3, -2, 4]

Output: 6

The subarray [2,3] has the largest product 6.

Solution

The key to this problem is to realize that the maximum product can be formed by either a positive number multiplied by a previous maximum product, or a negative number multiplied by a previous minimum product. Therefore, we need to keep track of both the maximum and minimum product ending at the current position.

Algorithm Steps

Initialize `max_so_far`, `min_so_far`, and `result` to the first element of the array.
Iterate through the array from the second element.
For each element, the new `max_so_far` is the maximum of the element itself, the element multiplied by the previous `max_so_far`, and the element multiplied by the previous `min_so_far`.
Similarly, the new `min_so_far` is the minimum of these three values.
Update the overall `result` with the new `max_so_far`.
Return `result`.

Maximum Product Subarray

Dynamic Programming Approach

Input: nums = [2, 3, -2, 4]

Output: 0

Progress1 / 1

Ready to start the visualization

Nums

-2

Max So Far

Min So Far

Maximum Product Subarray Solution


class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        if not nums:
            return 0
        
        max_so_far = nums[0]
        min_so_far = nums[0]
        result = max_so_far
        
        for i in range(1, len(nums)):
            curr = nums[i]
            temp_max = max(curr, max_so_far * curr, min_so_far * curr)
            min_so_far = min(curr, min_so_far * curr, max_so_far * curr)
            
            max_so_far = temp_max
            
            result = max(max_so_far, result)
            
        return result