Maximum Product Subarray
Given an integer array nums, find the contiguous subarray within an array(containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest of product 6.
Solution
The trick in this solution is to maintain a maximum and minimum value to cater for the negative values. Otherwise if it was only positives then we can outrightly say the largest product will involve all the array items.
Here's the solution.
# time complexity : O(n) | space complexity : O(1)
def max_product(self, nums: List[int])->int:
res = max(nums)
curMin, curMax =1, 1
for n in nums:
if n == 0:
continue
tmp = curMax * n
curMax = max(tmp, n * curMin, n)
curMin = min(tmp, n * curMin, n)
res = max(res, curMax, curMin)
return res
Testing
The following is a unit test to validate that our code works as we claim it does!
class TestMaximumProductSubarray(unittest.TestCase):
def __init__(self, methodName: str = "runTest") -> None:
super().__init__(methodName)
self.sol = Solution()
def test_max_product(self):
self.assertEqual(6, self.sol.max_product([2,3,-2,4]))
self.assertEqual(768, self.sol.max_product([0, 2,-3,-2,4,-1, 96]))
if __name__=="__main__":
unittest.main()