Maximum product subarray

Largest product of a contiguous run of numbers. A negative value can turn the smallest product into the largest.

The idea

Unlike a sum, a product can flip sign. So track both the best (most positive) and worst (most negative) product ending at each index. A negative number swaps their roles, because multiplying the most negative value by another negative gives the new most positive one.

Code

public static int MaxProduct(int[] a) {
    int maxEnd = a[0], minEnd = a[0], best = a[0];
    for (int i = 1; i < a.Length; i++) {
        if (a[i] < 0) (maxEnd, minEnd) = (minEnd, maxEnd);
        maxEnd = Math.Max(a[i], maxEnd * a[i]);
        minEnd = Math.Min(a[i], minEnd * a[i]);
        best = Math.Max(best, maxEnd);
    }
    return best;
}

Tips

• Keep both a running max and a running min ending at the current index, not just one.
• If any element is 0, both running values reset to 0 there, since no product can cross a zero.

In the .NET library

Forgetting the running minimum is the classic bug: code that tracks only the maximum misses cases where two negatives multiply into a new best, like 3, -2 after -4 giving a bigger product than either alone.