Leetcode September Day11
Shailesh Kumar
Posted on September 11, 2020
Question - 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: 6
Explanation: [2,3] has the largest product 6.
"""
Naive Solution -
Iterate over all possible sub arrays and return the maximum.
Code -
def maxProduct(self, nums: List[int]) -> int:
ans = float('-inf')
for i in range(len(nums)):
for j in range(i, len(nums)):
ans = max(ans, reduce(lambda x,y: x*y, nums[i:j+1]))
return ans
Time Complexity = O(n^2)
A better solution is to maintain two variables, to store maximum and minimum product ending at current position.
Then we traverse the array once and for every index i in the array, we update the maximum and minimum product ending at A[i]. We update the result if maximum product found at any index is greater than the result.
def maxProduct(self, nums: List[int]) -> int:
# to store the max and min ending till the previous index.
max_ending, min_ending = 1, 1
# to store the maximum result so far
max_so_far = min(nums)
for num in nums:
temp = max_ending
# update the max product ending at current index
max_ending = max(num, max(num * max_ending, num* min_ending))
# update the minimum product ending at current index
min_ending = min(num, min(num * temp, num * min_ending))
max_so_far = max(max_so_far, max_ending)
return max_so_far
Posted on September 11, 2020
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
