Bug Report for maximum-product-subarray #4729
Description
Bug Report for https://neetcode.io/problems/maximum-product-subarray
The test cases for this question are not sufficient.
The following code passes all test cases:
class Solution:
def maxProduct(self, nums: List[int]) -> int:
localMax = nums[0]
actual = nums[0]
for num in nums[1:]:
actual *= num
localMax = max(localMax, actual, num)
nums.reverse()
localMax2 = nums[0]
actual2 = nums[0]
for num in nums[1:]:
actual2 *= num
localMax2 = max(localMax2, actual2, num)
return max(localMax, localMax2)
This is very similar to the prefix-suffix example solution.
The thing it's missing (that the example solution does have) is a zero check.
If I write a custom test case to illustrate such as:
nums=[10,0,5,6,0,10]
You can see that the biggest local maximum (30 = 5 * 6) is shielded by zeros, and that the individuals values of the product (5 and 6) are not larger than the global maxes to date (10, from either side) so the third term in the max() function calls does not overwrite our local max values.
The evaluator code correctly returns 30 for this case but the above code snippet would return 10 (yet it passes the test suite for the problem).
Recommended resolution:
Add a test case such as:
nums=[10,0,5,6,0,10]
This checks for a zero-shielded local maximum that arises specifically from a product and not a singular value (ex. nums=[10,0,30,0,10]).