Given an integer array nums
, find a subarray that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
Example 1:
Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums
is guaranteed to fit in a 32-bit integer.This problem asks to find the maximum product of a subarray within a given integer array. A naive approach would involve checking all possible subarrays, leading to a time complexity of O(n^3). However, a more efficient dynamic programming approach can solve this in O(n) time.
Approach:
The core idea is to track two values for each position i
in the array:
f[i]
: The maximum product ending at index i
.g[i]
: The minimum product ending at index i
.We initialize both f[0]
and g[0]
to nums[0]
. For each subsequent index i
, we consider three possibilities:
nums[i]
itself.f[i-1] * nums[i]
).g[i-1] * nums[i]
).f[i]
is the maximum of these three, while g[i]
is the minimum. The reason we need to track the minimum is because multiplying two negative numbers results in a positive number, potentially leading to a larger product. The overall maximum product is the maximum value encountered across all f[i]
.
Time Complexity Analysis:
The solution iterates through the input array nums
once. Therefore, the time complexity is O(n), where n is the length of the array.
Space Complexity Analysis:
The solution uses a constant amount of extra space to store variables (f
, g
, ans
). Therefore, the space complexity is O(1).
Code Explanation (Python):
class Solution:
def maxProduct(self, nums: List[int]) -> int:
ans = f = g = nums[0] # Initialize ans, f, and g to the first element
for x in nums[1:]: # Iterate from the second element
ff, gg = f, g # Store previous f and g values
f = max(x, ff * x, gg * x) # Update f: max of current element, product with previous max, product with previous min
g = min(x, ff * x, gg * x) # Update g: min of current element, product with previous max, product with previous min
ans = max(ans, f) # Update ans if a larger max product is found
return ans
The other language implementations follow the same logic; they just use different syntax for the max and min functions and array iteration. The core algorithm remains the same, offering efficient computation of the maximum product subarray.