Question - Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Explanation: [2,3] has the largest product 6.
Naive Solution -
Iterate over all possible sub arrays and return the maximum.
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