Leetcode September Day11

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