Bernice Waweru
Posted on February 26, 2022
Instructions
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.
Example
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Approach
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.
Python Implementation
def maxProduct(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
max_so_far = nums[0]
min_so_far = nums[0]
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.
💖 💪 🙅 🚩
Bernice Waweru
Posted on February 26, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
