Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
A subarray is a contiguous subsequence of the array.
Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
If you have solved the Maximum SubArray Sum, then you have some idea of how we can solve this problem.
We keep track of the minimum and maximum product of the numbers visited so far. Then we can make comparisons and update the variables appropriately.
def maxProduct(self, nums: List[int]) -> int: if len(nums) == 0: return 0 max_so_far = nums min_so_far = nums result = max_so_far for i in range(1, len(nums)): curr = nums[i] temp_max = max(curr, max_so_far * curr, min_so_far * curr) min_so_far=min(curr, max_so_far * curr, min_so_far * curr) max_so_far = temp_max result = max(max_so_far, result) return result
I hope you found this helpful.
Top comments (0)