Trouble Solving Maximum Product Subarray

Question

I am trying to solve LeetCode problem 152. Maximum Product Subarray:

Given an integer array nums, find a subarray^* that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Constraints:

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

---

* _{A subarray is a contiguous non-empty sequence of elements within an array.}

My approach to this was go two ways:

one way was to multiply the consecutive numbers

the other was to ignore the consecutive product and start multiplication from the current number

and here's my code for this approach(in python) :

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        
        def func(nums,i,rs):
            if i<0:
                return 1
            rs=nums[i]*rs
            res=max((func(nums,i-1,rs)),func(nums,i-1,rs=1))

            return res
        i=len(nums)-1
        rs=1
        return func(nums,i,rs)

    
x=Solution()

print(x.maxProduct([2,3,-2,4]))

I should be getting the answer as 6 (since the maximum product subarray will be [2,3]), however, I'm getting an output of 1. What's wrong with my code???

Answer 1

First of all, your general idea is a brute force algorithm. This is very inefficient, and will not pass the LeetCode tests even when you fix the issues with the wrong return values.

But as you asked specifically about these wrong outputs and what is causing them, let's analyse it.

Issues in your code

1. Always returning 1

Your base case -- when arriving at i < 0 -- always returns 1. And when coming back from recursion, the max of 1 and 1 is still 1, so also return res will return 1. There is actually no way this recursive function could return anything else than 1.

It doesn't matter that rs will often be different from 1. In the end it is not used to determine the final return value. You have a lot of multiplications going on, only to finally ignore that product.

The first fix is to not ignore that product, and return it in the base case:

            if i<0:
                return res  # Fix

Now your code will return 6 for the example input.

2. Missing the third way

After applying the above fix, your code will not return the correct value yet for other inputs, like these:

[3, -3, 4]
[-1, 1, 4]

The problem is that in your analysis of "two ways", there is a way missing: it is to not ignore the product so far, but consider it a candidate for the final result. In the above two examples, 4 is a valid candidate, but by ignoring it and starting with new products, you'll only find lesser products (in these examples), and return one of those. This is not good: 4 should get a chance to compare with those other products.

To fix that issue, your max() call should consider this "third way" as well, and include rs (without recursive call) as an argument to max(). That will make your function also work for the above kinds of inputs.

3. Assuming 1 as initial "product"

Then there are still other inputs for which your function will return the wrong result. For instance:

[-3, 0, -2]

The expected output here is 0, but your function will return 1, which in fact is a product you can never get from such input. The cause is your assumption that you can use rs=1 any time you start a new product -- both in the main call and in a recursive call. This works often, but not if a zero is involved. So starting with rs=1 is wrong. Always start with an actual value that is in the list, and then multiply that with a neighbor value, or don't. But not taking any value from nums and assuming that 1 is a solution is clearly wrong.

To fix that for what concerns the main call, change this:

        i=len(nums)-1
        rs=1

...to this:

        i=len(nums)-2  # We'll exclude the last value, because...
        rs=nums[-1]    # ...we take that as a value to work with, not 1.

You need a similar change in the recursive call. Change this:

func(nums,i-1,rs=1)

to this:

func(nums,i-1,rs=nums[i])  # Use a real value

This latter change, means that you include nums[i], and so you should exclude nums[i] from the "third way" discussed above.

Corrected code

After applying the above fixes to your code, we get this:

    def maxProduct(self, nums: list[int]) -> int:
        def func(nums,i,rs):
            if i < 0:
                return rs # Return the product that was accumulated
            # Consider three ways:
            #   1. Stop at the current accumulated product, not including the current index
            #   2. Continue aggregating the product
            #   3. Start a new product at the current index (don't use 1)
            return max(rs, func(nums, i-1, nums[i]*rs), func(nums, i-1, rs=nums[i]))

        i = len(nums)-2  # We'll exclude the last value, because...
        rs = nums[-1]    # ...we take that as a value to work with, not 1.
        return func(nums, i, rs)

This will return the correct response if enough space and time resources are available.

Brute force is not good enough

Your approach is really a brute force algorithm. All possible sublists are considered and the products they represent are calculated and compared. This is not efficient, and will not pass the LeetCode tests that provide a nums list with 50 entries. Note that LeetCode will supply lists with up to 104 entries, so 50 really isn't a lot.

Also, the recursion depth will become a problem, as the default stack limit will be reached before reaching the base case for larger inputs.

You'll have to come up with an entirely different algorithm.

Hints:

• If a list has no zeroes, then you'll want to find a sublist that has an even number of negative values as then the product will be positive. Within that constraint, you'll want that list to include as many numbers as possible, as adding more numbers will not decrease the product (again, if we keep the number of negative values even). If the number of negative values is odd, then you'll want to either start the product after the first negative number, or stop before the last negative number.

• If a list has zeroes, then solve the problem for the sublists between those zeroes, and then see if the maximum product for those is greater than 0, otherwise stick with 0.

Spoiler solution:

def maxProduct(self, nums: list[int]) -> int: def product(start, stop): p = 1 for i in range(start, stop): p *= nums[i] return p neg_count = start = 0 # Initialise info about first partition best = max(nums) # This considers all sublists of size 1 if nums[-1]: nums.append(0) # Add a zero-stub for i, val in enumerate(nums): if val < 0: # Track info on negative numbers in this partition if not neg_count: first_neg_idx = i last_neg_idx = i neg_count += 1 if val: continue # Deal with each partition delimited by zeroes if i - start > 1: if neg_count % 2 == 0: # Even negative value count # Take all numbers in the partition p = product(start, i) elif neg_count > 1: # Odd, but not 1 # Either start after first negative, # or stop before last p = product(first_neg_idx + 1, last_neg_idx) * min( product(start, first_neg_idx + 1), product(last_neg_idx, i) ) elif start == first_neg_idx: # Exclude negative at start of this partition p = product(start + 1, i) elif first_neg_idx == i - 1: # Exclude negative at end of this partition p = product(start, first_neg_idx) else: # Exclude negative: choose greatest product p = max(product(start, first_neg_idx), product(first_neg_idx + 1, i)) best = max(best, p) # Start a new partition start = i + 1 neg_count = 0 return best