When one running value is not enough

If a bad value can become good, you have to carry it too.

Why it works

Carry both, and consider starting fresh

Keep two running values ending at the current position: the largest and the smallest. At each step, the new candidates are the element alone, the element times the previous largest, and the element times the previous smallest.

Take the maximum of those three for the new largest and the minimum for the new smallest. The element alone is what allows a run to restart, which matters whenever the running value has become useless.

1# The running high and low from everything up to here.2high, low = 3, -63value = -44 5candidates = (value, value * high, value * low)6print("start fresh, extend the high, extend the low:", candidates)7print("new high:", max(candidates), " new low:", min(candidates))

The new best comes from the old *worst*. Tracking only the high would have missed 24 entirely.

Predict the output· 5 min

Predict the output: tracking only the best

This carries a single running best, the way the sum version does. Type the two values it prints, separated by a single space.

Python

1def largest_run_product_broken(values):2    best = running = values[0]3    for value in values[1:]:4        running = max(value, running * value)5        best = max(best, running)6    return best7 8print(largest_run_product_broken([2, 3, -2, 4]), largest_run_product_broken([-2, 3, -4]))

Printed output

Problem· 25 min

Maximum Product Subarray

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1# The running high and low from everything up to here.2high, low = 3, -63value = -44 5candidates = (value, value * high, value * low)6print("start fresh, extend the high, extend the low:", candidates)7print("new high:", max(candidates), " new low:", min(candidates))

1def largest_run_product_broken(values):2 best = running = values[0]3 for value in values[1:]:4 running = max(value, running * value)5 best = max(best, running)6 return best7 8print(largest_run_product_broken([2, 3, -2, 4]), largest_run_product_broken([-2, 3, -4]))