Leetcode: 152. Maximum Product Subarray

• Pattern: Find cumulative product of an array.
• Pattern: Find optimal subarray.

• Is there an alternative problem easier to solve?
• Can we solve the problem by iterating from left to right (or right to left)?

Have I solved a similar problem? Yes, I solved Leetcode: 53. Maximum Subarray which is about finding the subarray with maximum Cumulative Sum. But I discarded it since I failed in past to transfer ideas from problems that use additions or subtractions to similar problems that use multiplications and divisions; I couldn't keep the same time complexity or needed extra memory. Then I decided to go for a quadratic solution due the problem's constraints of \(|nums|=n \le (2 \times 10^4)^2 = 4 \times 10^8\). Fix the left index of the subarray and search for the best right index. While searching for the best right index, extend the Cumulative Product for each new index, and update the answer accordingly. The solution timed out what sent me back to the blackboard.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans, N = nums[0], len(nums)
        for i in range(N):
            cur = 1
            for j in range(i, N):
                cur *= nums[j]
                ans = max(ans, cur)
        return ans

Time to simplify the problem. What variations of this problem do I know how to solve?

• If all numbers are positive, the answer is the product of all numbers.
• If all numbers are negative, the answer is the product of all numbers if and only if \(n\) is even otherwise it is either \(nums[1,..,(n-1)]\) or \(nums[0,...,(n-2)]\).
• If there is a zero at position \(i\), the best subarray is either on \(nums[0,..,i-1]\) or \(nums[i+1, ...,n-1]\) because any subarray that contains zero has a zero Cumulative Product.

As we need a linear solution for the problem, let's apply the linear version of Fix One and Search Other Template: for each \(i\) representing the right-most indexed of the subarray, search the right-most index \(j\) in constant time.

Let's find \(j\) by keeping two segments negative and total subarray called respectively \(neg\) and \(t\). The total subarray is the proper \(nums[i,i+1,...,j]\). And the negative subarray is the prefix of total subarray with the largest negative product. For sure, \(product(t)\) is a candidate for solution. If the total subarray product is negative, then \(product(t) / product(neg)\) is also a candidate since this is the largest product of all suffixes of \(t\). For this solution to work, we have to carefully reset the subarray when \(product(t)=0\). Time complexity is \(O(n)\) and space complexity is \(O(1)\).

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        neg, ans, cur = -inf, nums[0], 1
        for n in nums:
            cur = cur * n or n
            ans = max(ans, cur, cur // (neg if neg != -inf else 1))
            if cur < 0:
                neg = max(neg, cur)
            elif cur == 0:
                neg, cur = -inf, 1
        return ans

Be \(maxp_{i-1} = nums[p] \times nums[p+1] \times ... \times nums[i-1]\) the maximum possible product ending on \(i-1\) and \(minp_{i-1} = nums[q] \times nums[q+1] \times ... \times nums[i-1]\) the minimum possible product ending on \(i-1\). Note that the problem is solved if we can compute \(maxp_{n-1}\). How can we extend the solution for i to i+1? The maximum possible product ending on \(i\) is either \(nums[i]\) if the product started on \(i\), \(nums[i] \times maxp_{i-1}\) if the product extends the maximum product so far or \(nums[i] \times minp_{i-1}\) if the minimum product so far became positive when multiplied by \(nums[i]\). The minimum possible product ending on \(i\) is the minimum of the same values.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maxp = minp = ans = nums[0]
        for n in nums[1:]:
            maxp, minp = max(n, maxp * n, min * n), min(n, minp * n, maxp * n)
            ans = max(ans, maxp)
        return ans

• Interview preparation: V