Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 152 Maximum Product Subarray - Problem Statement

Read the problem

Given an integer array numsnums, find the contiguous subarray with the largest product. Return that maximum product. For example, given [2,3,2,4][2, 3, -2, 4], the answer is 66 from the subarray [2,3][2, 3]. Given [2,0,1][-2, 0, -1], the answer is 00. You might think: "I know Kadane's algorithm for maximum subarray sum. Can I just adapt it?" Almost.

But products behave differently than sums. A negative number doesn't just decrease your product. It can flip the sign entirely. Before reading on, consider this: if you have a negative product and multiply by another negative number, what happens?