Maximum Product Subarray [LeetCode 152]

MaxProdSubArr.py

# Reference : https://www.youtube.com/watch?v=IOMjN6r7ju8

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        
        # NOTE: The crux of the solution is
        # to look at the array from both the ends.
        # That is in forward and in reverse order.
        # Also one more important concept is
        # anything multiplied to 0 will loose
        # it's value, so avoid that at any cost.
        # The problem can be solved by getting continuous
        # products of consicutive elements from
        # both directions into two different array and
        # then taking max of max of both arrrays. Here
        # one of the array is the original array and 
        # another is the original array in reverse order.
        
        # Init
        n = len(nums)
        
        # Make a array of original array in reverse order
        numr = nums[::-1]
        
        # Scan through both the arrays
        for i in range(n):
            
            # Avoid mulitplying with 0, and
            # a continuous multiplication is
            # always starts from index 1 as
            # it needs previous element for
            # multiplication
            if i and nums[i] and nums[i-1]:
                nums[i] = nums[i] * nums[i-1]
                
            # Same concept as above    
            if i and numr[i] and numr[i-1]:
                numr[i] = numr[i] * numr[i-1]
                
        # Return the max of max of both the arrays.         
        return max(max(nums), max(numr))