Question
Given an integer array
nums, find a subarray that has the largest product, and return the product.The test cases are generated so that the answer will fit in a 32-bit integer.
Note that the product of an array with a single element is the value of that element.
Idea
- This is a max subarray problem so we want to implement something like Kadane’s Algorithm but this doesn’t directly work because of the negative’s that could exist in the array. For example, if an even amount of contiguous negatives exist, we want to multiply those negatives in individually since we know this would even out and result in a greater product
- We solve this one deficit by also keeping track of our minimum, where when we update our maximum, we also consider that our maximum could be our current num[i] multiplied by our minimum since we could have two negatives that could result in a greater positive magnitude
- Therefore, we have three actions, set maximum to be our current index multiplied by the max, our current index multiplied by the min, or reset maximum to our current index, the same goes with minimum. We also want to set our result to the max of our result and our current max