int maxProduct(int A[], int n) {
// store the result that is the max we have found so far
int r = A[0];
// imax/imin stores the max/min product of
// subarray that ends with the current number A[i]
for (int i = 1, imax = r, imin = r; i < n; i++) {
// multiplied by a negative makes big number smaller, small number bigger
// so we redefine the extremums by swapping them
if (A[i] < 0)
swap(imax, imin);
// max/min product for the current number is either the current number itself
// or the max/min by the previous number times the current one
imax = max(A[i], imax * A[i]);
imin = min(A[i], imin * A[i]);
// the newly computed max value is a candidate for our global result
r = max(r, imax);
}
return r;
}
Possibly simplest solution with O(n) time complexity


very nice . I guess a bit of more explanation would help people understand:
this is very similar to the " max cumulative sum subarray" problem. here you keep 2 values: the max cumulative product UP TO current element starting from SOMEWHERE in the past, and the minimum cumuliative product UP TO current element . it would be easier to see the DP structure if we store these 2 values for each index, like maxProduct[i],minProduct[i] .
at each new element, u could either add the new element to the existing product, or start fresh the product from current index (wipe out previous results), hence the 2 Math.max() lines.
if we see a negative number, the "candidate" for max should instead become the previous min product, because a bigger number multiplied by negative becomes smaller, hence the swap()

Awesome code. My code is something like below:
M[i] the maximal product ending at i'th element
N[i] the minimal product ending at i'th elementM[i] = max (A[i], A[i] > 0 ? A[i] * M[i1] : A[i] * N[i1])
N[i] = min (A[i], A[i] > 0 ? A[i] * N[i1] : A[i] * M[i1])But your code to swap M[i] and N[i] is much cleaner.

@sonakshi4 it totally works. The answer is 24. BTW, OP this is so beautiful!!!