152. Maximum Product Subarray

How to solve Maximum Product Subarray (LeetCode 152): the approach in brief

The problem

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

Pattern

Maximum Product Subarray is a Dynamic Programming (DP) Patterns problem, in the 1D Array (Kadane's Algorithm for Max/Min Subarray) subpattern. The pattern covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break

Master Kadane's algorithm for finding maximum (or minimum) subarray sum in O(n) time.

Approach outline

1. Consider using dynamic programming to keep track of information as you iterate through the array.
2. Think about how the problem of finding the maximum product subarray is similar to the maximum sum subarray, and how Kadane's algorithm works.
3. Because the array contains negative numbers, consider tracking both the maximum and minimum products ending at each position to handle sign changes.

Complexity

The reference solution runs in O(n) time and O(1) space.

Asked at

Maximum Product Subarray has been reported in interviews at Amazon, LinkedIn, Google, Apple, Facebook, Akuna Capital.