Description
https://leetcode.com/problems/maximum-product-subarray/
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Explanation
need to keep track of min product and max product because both positive and negative numbers exist.
Python Solution
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums:
return 0
result = nums[0]
min_product = max_product = 1
for num in nums:
choices = num, min_product * num, max_product * num
max_product = max(choices)
min_product = min(choices)
result = max(result, max_product)
return result- Time complexity: ~N
- Space complexity: ~1