Practice/Microsoft/Leetcode 152. Maximum Product Subarray

Leetcode 152. Maximum Product Subarray

CodingMust

Problem

Given an integer array, find the contiguous subarray within the array that produces the largest product, and return that product value.

A contiguous subarray means consecutive elements from the original array. You need to handle arrays that may contain positive numbers, negative numbers, and zeros.

Requirements

1. Return the maximum product achievable from any contiguous subarray
2. Handle arrays containing positive integers, negative integers, and zeros
3. Consider that the product of two negative numbers becomes positive
4. Account for zeros breaking the continuity of products
5. The array will contain at least one element

Constraints

• 1 ≤ nums.length ≤ 20,000
• -10 ≤ nums[i] ≤ 10
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer
• Aim for O(n) time complexity and O(1) space complexity

Examples

Example 1:

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

Example 2:

Input: nums = [-2, 0, -1] Output: 0 Explanation: The maximum product is 0, which comes from the element 0 itself.

Example 3:

Input: nums = [-2, -3, -4] Output: 12 Explanation: The subarray [-3, -4] yields the maximum product of 12.

Example 4:

Input: nums = [0, 2] Output: 2 Explanation: The subarray [2] gives the maximum product.