Maximum Product Subarray
Asked byLinkedInAmazonMicrosoftBloombergInfosysGoogle
Problem
Given an integer array nums, find the contiguous subarray with the largest product and return that product.
Examples
Example 1
Input:nums = [2,3,-2,4]
Output:6
[2,3] has the largest product.
Example 2
Input:nums = [-2,0,-1]
Output:0
Constraints
- 1 <= nums.length <= 2 * 10^4
Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.
Solve on FeatCode →How to approach it: the 1-D Dynamic Programming pattern
Break a problem into overlapping subproblems along a single dimension — like "the answer up to index i" — solve each one once, and reuse the result instead of recomputing it.
Look for this pattern when
- A greedy or purely recursive approach recomputes the same subproblem repeatedly.
- The problem asks for a count, a minimum/maximum, or a yes/no reachability over a sequence, where the answer at position `i` depends on answers at earlier positions.
Read the full 1-D Dynamic Programming guide →
Video walkthroughs
Original problem on LeetCode ↗
More 1-D Dynamic Programming problems