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
 ^
 i

[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
        ^^
        ij

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

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]
          j+=1
        else:
          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)
  print(s([-2,0,-1]),0)