maximum_product_subarray.py

classSolution:

# main idea: dynamic programming (DP)
# Besides keeping track of the largest product, 
# we also need to keep track of the smallest product.
# be careful: 'contiguous' subarray

defmy_product(self,nums):

# special case
iflen(nums)==1:
returnnums[0]

# initialization
my_max= [0for_inrange(len(nums))]
my_min= [0for_inrange(len(nums))]
print(my_max)
print(my_min)

# set the base
my_max[0] =nums[0]
my_min[0] =nums[0]

# need to initialize the 'final_max'
final_max=nums[0]

foriinrange(1, len(nums)):
# update 'max' and 'min'
my_max[i] =max(my_max[i-1]*nums[i], my_min[i-1]*nums[i], nums[i])
my_min[i] =min(my_max[i-1]*nums[i], my_min[i-1]*nums[i], nums[i])
# need to update the 'final_max'
final_max=max(final_max, my_max[i])

returnfinal_max

defmaxProduct(self, nums: List[int]) ->int:

# test case
#test_input = [-4,-3]
#test_result = self.my_product(test_input)
#print(test_result)

result=self.my_product(nums)
returnresult