Maximum Product Subarray: Track the Minimum Too
by linkjobai
HTML
<h1>Maximum Product Subarray: Track the Minimum Too</h1>
<p>Maximum Product Subarray looks like Kadane's algorithm, and it nearly is, with one twist: a negative number turns the smallest product into the largest.</p>
<p>So keep two running values at each index: the maximum product ending here and the minimum product ending here. For the next number x, the candidates are x, x * max, and x * min. The new max is the largest of those, the new min the smallest.</p>
<p>Compute both from the old values before overwriting either one, or use a swap when x is negative. Overwriting too early is the classic bug.</p>
<p>Zeros reset everything naturally, because x alone becomes a candidate.</p>
<p>A second approach that interviewers enjoy: the answer is always a prefix or suffix product within a zero-free segment. Scan left to right and right to left, resetting the running product at zeros, and take the max. It is O(n) and very easy to prove.</p>
<p>Test with [2,3,-2,4], [-2,0,-1], and [-2,3,-4] to cover the sign flip and the zero reset.</p>
<p>Disclosure: I work on Linkjob AI. If you want to rehearse explaining problems like this with live hints, try <a href="https://www.linkjob.ai/">Linkjob AI copilot</a>.</p>