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


  • 3
    F

    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.


  • 0
    L

    @fiedler Good explanation dude! Appreciate it.


Log in to reply
 

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