Arrays and Hashing One pass with running state
72. Maximum Product Subarray
You are given an array of integers nums. Return the largest product you can get by multiplying together the
elements of one subarray.
A subarray is a contiguous, non-empty part of nums. Its product is all of its elements multiplied
together, so a subarray of one element has that element as its product.
Example 1
Input: nums = [2, -5, -2, 3, 0, 4]
60Explanation: The first four elements multiply to 2 × (−5) × (−2) × 3 = 60, because the two negative numbers cancel out. The 0 cuts the array in two, and the part after it only reaches 4.
Example 2
Input: nums = [-3]
-3Explanation: The only subarray is [-3], so the answer is negative. A subarray cannot be empty.
Example 3
Input: nums = [-2, 0, -1]
0Explanation: [-2] and [-1] are negative, and every subarray that holds the 0 has product 0. The best you can do is
0.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-10 ≤ nums[i] ≤ 10- The product of every subarray of
numsis between-1018and1018.
Clarifying questions
What you would ask an interviewer before writing any code.