Maximum Product Subarray

Maximum Product Subarray

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

A subarray is a contiguous subsequence of the array.

Example

Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.

Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Approach 1 (Failed):

Like the MaximumSubarray question I solved yesterday, I thought that I would be able to solve this question by keeping track of which elements would actually maximize the product. However, unlike addition in which I should only consider if an addition of a negative number will maximize or minimize the result, I had more things to consider.

Having a zero in the middle of the array meant that nums array would be separted by that zero element, unless zero is the maximum value that nums can yield like the second example.

With a negative value, I thought I had a clever idea to keep track of it.

1. Iterate through the nums list with an integer variable ‘curr’ that keeps on multiplying the elements
2. If ‘curr’ is negative, save that negative value to a new integer variable ‘min’ that keeps that value until ‘curr’ encounters another negative value
3. Reset ‘curr’ as 1 since ‘curr’ might never encounter negative value
4. If ‘curr’ does encounter another negative value, update ‘curr’ so that it also multiplies from the previous ‘min’

With this approach, I would not be able to include the last negative value from the list in the product even if it will make up the largest product if the number of negative number becomes odd.

Ex) [2,-5,-2,-4,3] should return 24 whereas my implementation returns 20.

Approach 2:

Since I spent more than 45 minutes on this question, I thought it would be better to look at the solutions.

I knew there can be a brute-force solution that iterates the list with another inner for-loop to check every product. I also knew that this O(n^2) operation will be too slow to pass the tests.

There was another clever solution, which is similar to my apprach 1, but kept track of the most negative (minimum) value, not just any negative value from the list. By doing so, whenever ‘curr’ encounters negative number, it can update corretly by multiplying with that minimum value.

Implementation:

class Solution:
    

    def maxProduct(self, nums):
        maxima = minima = result = nums[0]
        for i in range(1, len(nums)):
            curr = nums[i]
            temp = max(curr, curr*maxima, curr*minima)
            minima = min(curr, curr*maxima, curr*minima)
            maxima = temp
            result = max(maxima, result)
        return result

Complexity Analysis:

Time Complexity:O(n) where n is the length of the list

Space Complexity: O(1)

Reflection

I was kind of bummed out when I thought I had a really clever solution, just to find out that it does not work. However, I am thankful that I could improve this much after just 10 questions of Leetcoding and I am optimistic that I would be able to tackle these questions in the future!