DSA interview question

Maximum Product Subarray

Medium · Algorithms · Topics: array, dynamic programming

The problem

A bioinformatics tool models how a sequence of mutations scales a protein's activity: each mutation multiplies activity by an integer factor, which can be negative (an inhibitor flips the effect) or zero (it knocks the protein out). Researchers want the contiguous run of mutations with the largest combined product. Kadane's idea almost works, with one wrinkle: a very negative product can become the largest after one more negative factor. So you track both the largest and the smallest product of a subarray ending at each position.

Example: [2, 3, -2, 4] → 6 (the subarray [2, 3]).

Function signature

long long maxProduct(const vector<int>& nums);  // largest product of a non-empty contiguous subarray

Test cases

Input `nums`	Output	Explanation
`[2, 3, -2, 4]`	6	`[2, 3]`
`[-2, 0, -1]`	0	`[0]`
`[-2, 3, -4]`	24	Two negatives make a positive
`[-2]`	-2	A single negative element
`[0, 2]`	2
`[-1, -3, -10, 0, 60]`	60	Zero splits the array
`[2, -5, -2, -4, 3]`	24	`[-2, -4, 3]`

(Confirm: the subarray is non-empty; the answer fits in a 64-bit integer.)

How interviewers phrase it

"Find the contiguous subarray with the largest product" (LeetCode 152).
Asked after Kadane's algorithm, to see whether you notice that negatives break the simple max-only approach.

Clarifying questions to ask

Can values be negative or zero?
Must the subarray be non-empty?
How large can the product get? (Overflow.)

Follow-ups to expect

"Why track the minimum as well?"
"What does a zero do?"
"Is there another O(n) solution?"
"How does this relate to Kadane's?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview