152. Maximum Product Subarray

Problem¶

Given a nonempty integer array, return the maximum product of any contiguous subarray.

nums = [2, 3, -2, 4] -> 6 from [2, 3]

Key trick¶

Track both the maximum and minimum products ending at each position, because multiplying by a negative number swaps their roles.

Trap¶

Tracking only the current maximum misses cases where a negative minimum becomes the next maximum.
Zeros must restart the current product.
Enumerating all subarrays takes \(O(n^2)\) time and causes a timeout.

Why is it interesting?¶

It is a variation of Kadane's algorithm where sign changes require maintaining two states instead of one.

Python solution¶

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

        for x in nums[1:]:
            # A negative integer turns the smallest product into the largest.
            if x < 0:
                cur_max, cur_min = cur_min, cur_max

            # Starting a new subarray also handles zeros.
            cur_max = max(x, cur_max * x)
            cur_min = min(x, cur_min * x)

            best = max(best, cur_max)

        # Time: O(n), space: O(1).
        return best

Comment on my solution¶

Your dynamic programming recurrence enumerates every contiguous subarray product, and the ascending inner loop correctly preserves the needed previous value at dp[i + 1].

The result is correct, but the nested loops make it \(O(n^2)\) time, which explains the timeout on long inputs such as an array of ones. Space usage is \(O(n)\), while tracking only the current minimum and maximum reduces it to \(O(1)\).

# DON'T WORK
# Time Limit Exceeded: 188/191 testcases passed
# Error with input [1,1,1,...]
class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        # [2,3,-2,4] -> 6 (because of [2,3])
        # [-2,0,-1]  -> 0 (because [-2,-1] is not a subarray)

        # - sliding windown
        # - variation of Kadane's algo?
        #     best = nums[0]
        #     curr = nums[0]
        #
        #     for x in nums[1:]:
        #         curr = max(curr * x, x)
        #         best = max(best, curr)
        #   - [2,3,-2,4,-1] -> 48 (take the whole array)
        #     - pure Kadan's algo would return 6 ([2,3])
        # - dp
        #   dp[i][j] = 1 # for i > j
        #   dp[i][i] = nums[i]
        #   dp[i][j] = dp[i+1][j-1] * nums[i] * nums[j] # i < j
        #
        #   [2,3,-2,4]
        #   2 6 -12 -48
        #     3 -6  -24
        #       -2  -8
        #            4
        #   dp[i][j] = 1 # for i > j
        #   dp[i][i] = nums[i]
        #   dp[i][j] = dp[i-1][j+1] * nums[i] * nums[j] # i > j
        #
        #     2
        #     6  3
        #   -12 -6  -2
        #   -48 -24 -8  4

        n = len(nums)
        dp = [1] * n
        best = nums[0]

        for j in range(n):
            for i in range(0,j+1):
                if i == j:
                    dp[i] = nums[i]
                else:
                    dp[i] = nums[j] * nums[i] * dp[i + 1]
                best = max(best, dp[i])
        return best