Maximum Product Subarray

Array
Medium

Approach

Diagrams

Analysis

Time

O(n)

Space

O(1)
class Solution:
    def maxProduct(self, nums):
        minEndingHere = nums[0]
        maxEndingHere = nums[0]

        maxProductSoFar = nums[0]

        for idx in range(1, len(nums)):
            num = nums[idx]

            prevMin, prevMax = minEndingHere, maxEndingHere

            minEndingHere = min(num, prevMin * num, prevMax * num)
            maxEndingHere = max(num, prevMin * num, prevMax * num)

            maxProductSoFar = max(maxProductSoFar, maxEndingHere)

        return maxProductSoFar

Learn

#Array

#Kadane's Algorithm

Videos