LeetCode 152: Maximum Product Subarray, Deriving Two DP States from a Negative Counterexample
Problem Requirements Given an integer array nums, find a nonempty contiguous subarray with the greatest product and return that product. Contiguous means the chosen elements must be adjacent: you cannot skip a number in between. Nonempty means you must choose at least one element. Return only the product, not the range or its length. Input: nums = [2, 3, -2, 4] Output: 6 Explanation: The contiguous subarray [2, 3] has the greatest product, 2 * 3 = 6. Input: nums = [-2, 0, -1] Output: 0 Explanation: You cannot skip 0 and treat -2 and -1 as a subarray. Choosing [0] gives 0. The constraints are 1 <= len(nums) <= 20000 and -10 <= nums[i] <= 10. The problem guarantees that the product of any subarray fits in a signed 32-bit integer. The input is never empty, but it may contain negatives and zeros. ...