moonlightshadow123
5/30/2017 - 2:58 PM

152. Maximum Product Subarray

  1. Maximum Product Subarray

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxSoFar = -float('inf')
        maxEndingHere = 1
        minEndingHere = 1
        for num in nums:
            temp = max(maxEndingHere*num, num, minEndingHere*num)
            minEndingHere = min(maxEndingHere*num, num, minEndingHere*num)
            maxEndingHere = temp
            maxSoFar = max(maxEndingHere, maxSoFar)
        return maxSoFar

https://leetcode.com/problems/maximum-product-subarray/

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.