Given an integer array , find the contiguous subarray with the largest product. Return that maximum product. For example, given , the answer is from the subarray . Given , the answer is . You might think: "I know Kadane's algorithm for maximum subarray sum. Can I just adapt it?" Almost.
But products behave differently than sums. A negative number doesn't just decrease your product. It can flip the sign entirely. Before reading on, consider this: if you have a negative product and multiply by another negative number, what happens?