Contiguous subarray with the largest product (array may include negatives and zeros).
[1,2,3,4,5,0] → 120.
Brute force: every subarray’s product directly — O(n³), reducible to O(n²) with a running product per start index.
Optimal — prefix/suffix products: a fully positive array (or one with an even count of
negatives) has its max product from the whole array. An odd count of negatives means exactly one
negative needs excluding — but you don’t know which, so track products from both directions
(pre from the left, suff from the right) simultaneously; whichever direction “skips” the
problematic negative or a 0 will surface the answer. Reset a running product to 1 whenever it
hits 0 (multiplying through a zero is useless).
public static int maxProductSubArray(int[] arr) { int n = arr.length; int pre = 1, suff = 1; int ans = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) { if (pre == 0) pre = 1; if (suff == 0) suff = 1; pre *= arr[i]; suff *= arr[n - i - 1]; // from the back ans = Math.max(ans, Math.max(pre, suff)); } return ans;}Time: O(n). Space: O(1).