Maximum Product Subarray

Medium Subject: 1-D Dynamic Programming

Time Complexity

O(N)

Space Complexity

O(1)

Problem Description

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.

Example 1:

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

Optimal Solution

Python

Approach: DP tracking Max and Min

Because a negative number can turn a minimum product into a maximum, we track both the current max and current min product ending at each position. We update them based on the current number, the current max, and the current min.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        cur_max = cur_min = global_max = nums[0]

        for i in range(1, len(nums)):
            n = nums[i]
            vals = (n, n * cur_max, n * cur_min)
            cur_max = max(vals)
            cur_min = min(vals)
            global_max = max(global_max, cur_max)

        return global_max