The Multiplier Rush

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Spirit Airlines

Problem

An on-call engineer suspects the gain report understates the strongest section of an amplifier chain whose stages include inverting (negative) and muted (zero) gains. From the per-stage integer gains in nums, listed in chain order, return the largest product over any run of consecutive stages, and 0 for an empty chain.

Negatives cancel negatives - but only if you keep both in view.

Example 1

Input:

nums = [2,3,-2,4]

Output:

6

Example 2

Input:

nums = [-2,0,-1]

Output:

0

Worked solution and explanation

What this really is

Strip off the amplifier chain and this is maximum subarray with a sign problem built in. Everyone reaches for the one-pass scan from the sum version. What separates candidates is seeing that a single running best is not enough: an inverting stage turns the most negative running product into the largest one. Carry only the max and [-2, 3, -4] comes back as 3 instead of 24, and [-1, -2, -3] as 2 instead of 6. Seed the best from 0 or 1 instead of the first gain, and a lone [-5] reports a gain the chain does not have.

Building it

Step 1: Seed from the first gain, not from a neutral value

Return 0 for an empty chain up front, then set global_max, local_max and local_min to nums[0]. A run of one stage is valid, so the answer can be negative. Starting at 0 or 1 invents a run that never existed.

Step 2: Extend or restart at every stage

The best run ending at this stage is one of three: the stage alone (restart), the stage times the previous local_max, or the stage times the previous local_min. Take the max of the three as the new local_max and the min as the new local_min.

Step 3: Remember the best you have seen

After each stage, compare local_max against global_max. The best section can end anywhere, so the answer is the best of all the ending-here values, not the last one.

The solution

Running max and min product in one pass
def max_product_subarray(nums):
    if not nums:
        return 0
    global_max = nums[0]
    local_max = nums[0]
    local_min = nums[0]
    for i in range(1, len(nums)):
        num = nums[i]
        candidates = [num, num * local_max, num * local_min]
        local_max = max(candidates)
        local_min = min(candidates)
        if local_max > global_max:
            global_max = local_max
    return global_max
Max only
On [-2, 3, -4] the running best goes -2, 3, then max(-4, -12) = -4. The -6 that ended at the 3 is thrown away, and the answer comes out as 3.
Max and min
local_min holds -6 after the 3. At -4 the candidates are -4, -12 and 24, so local_max becomes 24 and the inverting pair is credited.

Common follow-up questions