105. Maximum Product Subarray

Medium · Array

Given an array of integers, find the contiguous subarray with the largest product. The subarray must contain at least one element.

Note that the product of a subarray can be very large or very small (negative). You need to track both the maximum and minimum product ending at each position, since a negative number multiplied by a large negative product can become a large positive product.

Examples

Example 1
Input: [2, 3, -2, 4]
Output: 6
Explanation: The subarray [2, 3] has the maximum product of 6.

Example 2
Input: [-2]
Output: -2
Explanation: The only subarray is [-2], so the maximum product is -2.

Constraints

• Standard input/output constraints apply