moonlightshadow123
5/30/2017 - 2:58 PM

152. Maximum Product Subarray

  1. Maximum Product Subarray
maxEndingHere_minEndingHere.py
content_copyfile_download

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
152-Maximum-Product-Subarray.md
content_copyfile_download
  • Rendered
  • Source

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.