Given an integer array nums, return the largest product of any contiguous non-empty subarray. Negatives are the whole game: two of them multiply into a positive, so the worst product so far can become the best one element later.
Examples
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3].
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Example 3:
Input: nums = [-2,3,-4]
Output: 24
Explanation: the whole array — the two negatives cancel.
Example 4:
Input: nums = [-2]
Output: -2
Constraints
1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
Every subarray product fits in a 32-bit integer.
Prerequisites
Dynamic programming — being able to say, in one sentence, what a single cell of your table MEANS. Everything else follows from that sentence. Rolling variables: when a state only looks back one or two steps, the table collapses to a couple of numbers.
How to think about it
1. Carry the Smallest Too Optimal
Intuition
With sums, the worst running total is useless; with products it is the most valuable thing you have, because one negative number turns the smallest product into the largest. So carry both the largest and smallest product ending here — and when the current number is negative, swap their roles before extending, since multiplying flips the order.
Algorithm
1. Start both running products at the first element. 2. For each next number, swap the running maximum and minimum if it is negative. 3. Extend each by multiplying, or restart from the number itself — whichever is better. 4. Track the largest value ever held.