LeetCode 152. Maximum Product Subarray Solution Python

leetcode_152.py

# LeetCode : 152
# PROBLEM: Given an integer array nums, 
# find a contiguous non-empty subarray within the array that has the largest product, and return the product.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # Similar to Kadane's Algorithm.
        # When to discard a temp array -> If product becomes 0
        
        # Problem arises if a subarray (with no zeros) has odd number of -ve numbers
        # The only 2 possibilities there, are either we either split on the first -ve number
        # Or the last -ve number.
        
        # Instead of keeping track of the first and the last numbers to start and stop on, we calcualte once
        # in both directions.
               
        
        
        def get_max(numbers):
            largest_prod = -inf
            current_prod = 1
        
            for num in numbers:
                current_prod *= num
                largest_prod = max(current_prod, largest_prod)
                
                # Reset if 0 is seen
                if current_prod == 0: current_prod = 1
            
            return largest_prod
        
        
        return max(
            get_max(nums), 
            get_max(reversed(nums))
        )