One-dimensional Dynamic Programming
When one running value is not enough
If a bad value can become good, you have to carry it too.
Key idea
Where a single running value fails
Carrying the best answer ending at each position works when extending a good answer keeps it good. That fails as soon as an operation can flip a bad value into a good one.
Multiplication by a negative is the standard case. The most negative running product, multiplied by another negative, becomes the largest. So the smallest value so far is not useless; it is a candidate.
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.
Gotcha
Compute both from the old values
high, low = max(candidates), min(candidates) uses the candidates built from the previous pair. Assigning high first and then computing low from the updated high is wrong and is the usual way this breaks.
Building the candidate tuple first makes the mistake impossible, which is why it is worth the extra line.
Tip
The input that separates the two solutions
Take [-2, 3, -4]. All three multiplied together give 24, and a solution carrying only the largest discards the negative running value at the second step and returns 3.
Any test input without two negatives separated by something cannot tell those two solutions apart. When a problem hinges on sign, make sure your own tests include the case that needs both negatives, because the examples in a prompt frequently do not.
Edge cases
Zero resets everything
A zero makes both running values zero, and the element-alone candidate is what lets the run restart afterward. On [-2, 0, -1] the answer is 0, because every non-empty run containing the zero is zero and both alternatives are negative.
Without the element-alone candidate, a zero would trap both running values at zero forever. That candidate is doing two jobs: restarting after a zero, and restarting after a run that has become worthless.
Key idea
The general lesson
Before settling on a single running value, ask whether any future operation could make a currently-bad value good. If yes, carry both extremes.
The same reasoning applies to running sums with a subtraction available, or to any accumulation where the operation is not monotone. Recognizing non-monotonicity is the trigger.
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.
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.