Given an integer array
nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Input: [2,3,-2,4] Output:
6Explanation: [2,3] has the largest product 6.
Input: [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
need to keep track of min product and max product because both positive and negative numbers exist.
class Solution: def maxProduct(self, nums: List[int]) -> int: if not nums: return 0 result = nums 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