understanding leetCode - 121. Best Time to Buy and Sell Stock - Ruby

the #max method for arrays returns the largest value in an array, so...[3, 7, 4].max will return 7 (the largest value)

value = [0, value].max 

This is basically returning whichever is larger (zero or value) and assigning it to value. So it replaces any negative quantity in value with zero, but leaves it alone if it is a positive value.

Another way to do the same thing...

value = 0 if value < 0

Note about the condition you must buy before you sell, so basically we found the maximum among max profits (each profit i is the max among differences between each price[i] and prices after i)

so a naive solution is 2 loops

max of [
 max-profit-0: max of p[1] - p[0], p[2] - p[0], ...
 max-profit-1: max of p[2] - p[1], p[3] - p[2], ...
 ....
]

but the solution you provide is brilliant, it just need only one loop by taking advantages of below things:

• profit between price 0 and price 2 == p[2] - p[0] == (p[1] - p[0]) + (p[2] - p[1])

  => that is the code value += (prices[i] - prices[i-1]) do about, it will count the profit between the current date j (current step) and the start date i as long as the different still positive.

• in case the sum above is positive at step 1 and 2: p[1] - p[0] > 0 and p[1] - p[0] + p[2] - p[1] > 0, that mean p[0] < p[1] and p[0] < p[2], we could conclude that for every p[j] after date 2 (j > 2), p[j] - p[0] always larger than p[j] - p[1] and p[j] - p[2], so we could continue count sum (profit) with the start index 0 and ignore 1 and 2, since this problem's target is finding the MAX, right ?

the code value = [0, value].max will return value as long as value is positive, then value keep move on.

• in case the sum above (or profit) is positive at step 1 and negative at step 2: (p[1] - p[0]) + (p[2] - p[1]) < 0 so p[2] - p[0] < 0 and p[1] - p[0] > 0, that mean p[2] < p[0] and p[0] < p[1].

• so we have p[2] < p[0] < p[1], obviously for each price p[j] after date 2 (j > 2), p[j] - p[2] always larger than p[j] - p[0] and p[j] - p[1], and so that we could ignore p[0] and p[1], since this problem's target is finding the MAX, right ?

  That why we could reset value to zero to start count profit again with the start index 2, now value from the code value += (prices[i] - prices[i-1]) in the next loop is actually p[3] - p[2], not p[3] - p[2] + p[2] - p[1]..., remember that we already cached the maximum profit of the range [0..2].

  That is the code value = [0, value].max do about, it'll return 0 if value is <= 0.

[7, 1, 5, 3, 6, 4]
 +  - # that mean you sure that profits 
      # between each [5, 3, 6, 4] and [7] always < with [1]
      # so reset with date 1

good solution!

A good way to understand a program is to simply step through it with pen and paper, while keeping track of all the (relevant) state. So, let's do just that.

In our case, the relevant state are the values of the two local variables profit and value as well as the iteration variable i and by extension prices[i] and prices[i-1]. We start out with both of them being initialized to the value 0 in lines 1 and 2 of the method. Then, lines 4–8 are the loop which does all the actual work; line 10 simply returns the result. It is easy to see that lines 5–7 are the ones doing all the work, so let's focus on those:

What actually happens when I do value = [0, value].max. ?

The easiest way to find out what a method does, is to read its documentation [note, technically, this method is not Enumerable#max but Array#max, but they behave the same in this example]:

Returns the object in enum with the maximum value.

So, in other words, the method does what its name suggests: it returns the maximum of the Enumerable.

Note that this is not a very idiomatic way to write the code. For example, it makes no sense to use max in line 6 and if in line 7 to do the same thing: stick to one or the other, do not confuse the reader by using two different things to do the same thing. Also manually iterating over a collection is practically never done in Ruby. This would be much better expressed using Enumerable#each_cons and e.g. Enumerable#max_by or Enumerable#reduce. Actually, the perfect solution would be to use a prefix sum aka scan, but unfortunately, that is not available in Ruby's core and standard libraries.

An idiomatic version would look more like this:

def max_profit(prices)
  prices.
    each_cons(2).
    reduce([0, 0]) do |(value, profit), (a, b)|
      [[temp = value + b - a, 0].max, [temp, profit].max] 
    do.
    last
end

or this:

def max_profit(prices)
  prices.
    each_cons(2).
    map {|a, b| b - a }.
    reduce([]) do |res, difference|
      res << [(res[-1] || 0) + difference, 0].max
    end.
    max
end