Maximum Product Subarray
Problem Description
Given an integer array nums, find the contiguous subarray that has the largest product and return the product.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6 (subarray [2,3])
Example 2:
Input: nums = [-2,0,-1]
Output: 0
DE Shaw Tier 3 — LC 152.
Key insight: negatives can flip max to min and vice versa. Track both curMax and curMin.
curMax = max(num, num*curMax, num*curMin)
curMin = min(num, num*curMax, num*curMin)
(compute with old curMax before updating)
Example Test Cases
Example 1
Input: [[2,3,-2,4]]
Expected: 6
Example 2
Input: [[-2,0,-1]]
Expected: 0
Example 3
Input: [[-2,3,-4]]
Expected: 24
Example 4
Input: [[2,-5,-2,-4,3]]
Expected: 24
Run your code to see the results