Understanding why you need to keep track of just the min and max previous values

• Most of other solutions here basically just state that you need to keep track of the min and max of the previous `i`, but it wasn't clear to me why that is the case. Here's how I figured it out for `nums = [-2, 1, 2, -3, 1, 3]`:

First write out a matrix with all of the possible subarrays and their products like this:

``````Example of how to calculate a column:
-2   1   2  -3   1   3
----------------------
-2*1*2*-3 = 12
1*2*-3 = -6
2*-3 = -6
-3 = -3

Full matrix:
----------------------
-2   1   2  -3   1   3
----------------------
-2  -2  -4  12  12  36
1   2  -6  -6  18
2  -6  -6  18
-3  -3  -9
1   3
3
``````

From here, it is easy to convince yourself that the product of the max product subarray ending at column `i` is either:

• just `nums[i]` (eg, the second column subarray is just `[1]`)
• the product `nums[i] * min[i-1]` (eg, fourth column is `[-2,1,2,-3]`)
• the product `nums[i] * max[i-1]` (eg, third column is `[1,2]`)

And from there, you have the recurrence relationship that the other solutions are using.

• @fiedler Good explanation dude! Appreciate it.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.