152. Maximum Product Subarray
Maximum Product Subarray (LeetCode 152) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (Kadane's Algorithm for Max/Min Subarray) subpattern.
- Blind 75 · #56 of 75 · 1-D Dynamic Programming
- NeetCode 150 · #107 of 150 · 1-D Dynamic Programming
- NeetCode 250 · #183 of 250 · 1-D Dynamic Programming
How to solve Maximum Product Subarray
Maximum Product Subarray is a Kadane's Algorithm problem, part of Dynamic Programming (DP) Patterns. Master Kadane's algorithm for finding maximum (or minimum) subarray sum in O(n) time.
Work towards the solution in these steps:
- Consider using dynamic programming to keep track of information as you iterate through the array.
- Think about how the problem of finding the maximum product subarray is similar to the maximum sum subarray, and how Kadane's algorithm works.
- Because the array contains negative numbers, consider tracking both the maximum and minimum products ending at each position to handle sign changes.
The reference solution runs in O(n) time and O(1) space.
The Maximum Product Subarray solution and editorial walks through the full approach with reference code.
Problem statement
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.
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 104
- -10 <= nums[i] <= 10
- The product of any subarray of nums is guaranteed to fit in a 32-bit integer.
Topics and companies
Topics: Array, Dynamic Programming.
Reported in interviews at Amazon, LinkedIn, Google, Apple, Facebook, Akuna Capital.
How to practise Maximum Product Subarray on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Maximum Product Subarray in the code editor, or read the Maximum Product Subarray editorial for a worked solution with its approach and complexity analysis.
Where Maximum Product Subarray sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- 1D Array (Kadane's Algorithm for Max/Min Subarray) subpattern
- The full DSA patterns sheet
Problems related to Maximum Product Subarray
Other problems that use the same 1D Array (Kadane's Algorithm for Max/Min Subarray) and Dynamic Programming (DP) Patterns techniques:
- Maximum Absolute Sum of Any Subarray — Medium, same subpattern
- Maximum Subarray — Medium, same subpattern
- Maximum Sum Circular Subarray — Medium, same subpattern
- Best Time to Buy and Sell Stock — Easy, same pattern
- Best Time to Buy and Sell Stock II — Medium, same pattern
- Best Time to Buy and Sell Stock III — Hard, same pattern
Maximum Product Subarray FAQ
What is the LeetCode number of Maximum Product Subarray?
Maximum Product Subarray is LeetCode problem 152, rated Medium.
What pattern is used to solve Maximum Product Subarray?
Maximum Product Subarray is a Kadane's Algorithm problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (Kadane's Algorithm for Max/Min Subarray) subpattern.
What is the time complexity of Maximum Product Subarray?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Maximum Product Subarray?
Maximum Product Subarray has been reported in interviews at Amazon, LinkedIn, Google, Apple, Facebook, Akuna Capital.