Friedrich Ewald My Personal Website

Leetcode: Maximum product subarray

Given an array nums with integer values -10 <= x <= 10, calculate the maximum consecutive product. For example, the array [2,3,-1,4] produces the maximum product 6 because 2*3=6. The first obsveration that we can make is that whenever a 0 is encountered, it sets the whole product to 0. This means, if a 0 is somewhere in the middle of the array, we need to look at the left and right part individually because they cannot be connected. Secondly, an odd amount of negative numbers makes the whole product negative. Having 2, 4,, 6, … negative numbers will keep the product at the same amount (if all of them are -1) or increase it. Finally, since those numbers are all integers, the longer the chain of multiplied numbers, the higher to outcome. The algorithm that I came up with iterates twice over the whole array and has a time complexity of O(n) and constant space complexity O(1). Given the following example [2,-2,3,-2,0,9] we can define two pointers, i and j and two helper variables, max_product and current_product. We start at position 0,0, then move the j pointer to the right and multiply the numbers that we encounter until we hit a 0. This way we slowly increment our product. At each step we compare the current product with the overal maximum. Once we reach the end or 0, we move i to the right and divide at each step until we reach j. If we reached a 0 we add this as possible maximum and then jump with i and j over the 0, starting the above process again.

[2,-2,3,-2,0,9] cur_prod=2, max_prod=2

[2,-2,3,-2,0,9] cur_prod=-4, max_prod=2
 ^  ^
 i  j

[2,-2,3,-2,0,9] cur_prod=-12, max_prod=2
 ^    ^
 i    j

[2,-2,3,-2,0,9] cur_prod=24, max_prod=24
 ^       ^
 i       j

[2,-2,3,-2,0,9] cur_prod=12, max_prod=24
    ^    ^
    i    j

[2,-2,3,-2,0,9] cur_prod=-6, max_prod=24
      ^  ^
      i  j

[2,-2,3,-2,0,9] cur_prod=-2, max_prod=24

[2,-2,3,-2,0,9] cur_prod=9, max_prod=24
             i  j
The Python code handles some more corner cases, for example if there’s only one element, and looks like this:
from typing import List

class Solution:
  def maxProduct(self, nums: List[int]) -> int:
    i,j = 0,0
    cur_prod = nums[0]
    max_prod = nums[0]
    while j < len(nums):
      cur_prod = nums[i]
      max_prod = max(max_prod, cur_prod)
      if cur_prod == 0:
        i += 1
      j += 1

      while i < j:
        if j < len(nums) and nums[j] != 0:
          cur_prod *= nums[j]
          if i + 1 < j:
            cur_prod //= nums[i]
          i += 1
        max_prod = max(max_prod, cur_prod)
    # max_prod = max(max_prod, cur_prod)

    return max_prod

if __name__ == '__main__':
  s = Solution().maxProduct
  print(s([2,3,-2,4]), 6)
  print(s([-2, 4, -2]), 16)
  print(s([-1,-2,-1,2,-2, -1]), 8)
  print(s([1,2,0,9]), 9)
  print(s([-1]), -1)
  print(s([10]), 10)

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.