Maximum Product Subarray

Given an integer array nums, return the largest product you can get from any non-empty contiguous subarray.

Input / output

• Input: nums: int[]
• Output: the maximum product as an integer

Examples

1. nums = [2, 3, -2, 4] returns 6 because the best subarray is [2, 3].
2. nums = [-2, 0, -1] returns 0 because every non-empty subarray has product -2, 0, or -1.
3. nums = [-2, 3, -4] returns 24 because the whole array multiplies to 24.

Constraints

• 1 <= nums.length <= 20000
• -10 <= nums[i] <= 10
• The answer fits in a 32-bit signed integer.

Edge cases

• A negative value can turn the smallest running product into the largest one.
• Zeros split the array into independent segments.
• The best answer may be a single element.

Target complexity

• Aim for O(n) time and O(1) extra space.

Hints

1. Track both the largest and smallest product ending at the current index.
2. When the next number is negative, those two running values swap roles.

Follow-up Why is tracking only the current maximum product insufficient once negative numbers are allowed?