Sign in
Skip to solution
mediumDSA

How do you find the maximum product subarray?

497 views
01

Understand the problem

Explain max product subarray.

dparrays
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Because negatives flip signs, track both the max and min product ending at each index (a min can become the max after multiplying by a negative). Update both each step and keep the global max. O(n) time, O(1) space.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Track running max and min
Run Playground
def max_product(nums):
    best = cur_max = cur_min = nums[0]
    for x in nums[1:]:
        if x < 0:
            cur_max, cur_min = cur_min, cur_max     # negative swaps roles
        cur_max = max(x, cur_max * x)
        cur_min = min(x, cur_min * x)
        best = max(best, cur_max)
    return best


# --- demo ---
print(max_product([2, 3, -2, 4]))   # 6   ([2,3])
print(max_product([-2, 0, -1]))     # 0
print(max_product([-2, 3, -4]))     # 24  (all three)
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 68 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track