Maximum Product Subarray

You are given an integer array nums. Pick one contiguous, non-empty subarray and return the largest product you can make from its elements.

The difficult part is that multiplication is not monotonic here:

  • a large positive product can become very negative after multiplying by a negative value
  • a very negative product can become the new best product after multiplying by another negative value
  • a zero breaks the chain and starts a new segment

That is why the solution must remember both the strongest and weakest product that end at each index.

Examples
Input: [2,3,-2,4]
Output: 6
Hints
Related Problems

Maximum Product Subarray

You are given an integer array `nums`. Pick one contiguous, non-empty subarray and return the largest product you can make from its elements.