The topic of dry

Given an array prices, prices[I] is the price of a given stock on day I.

Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example:

Prices = [7,1,5,3,6,4] If you buy it on day 2 (stock price = 1) and sell it on day 3 (stock price = 5), the exchange will make a profit of 5-1 = 4 and then buy it on day 4 (stock price = 3), Sell on day 5 (stock price = 6) and the exchange will make a profit = 6-3 = 3Copy the code

Greed

We can look at a chestnut:

The [1,2,3,4] array, the optimal solution is obviously 4-1=3, but how do we get this value through the entire path?

(2-1)+(3-2)+(4-3)=4-1 simplifies to get the result, so we can also compute all the optimal values in the path in this way. That is to say, we can use this way to calculate the return of a certain rising interval, which is also the idea of local optimal solution.

Execution time: 84 ms, beating 81.54% of all JavaScript commits

Memory consumption: 39.4 MB, beating 59.02% of all JavaScript commits

 var maxProfit = function (prices) {
    var profit = 0;
    for (var i = 0; i < prices.length; i++) {
      if (prices[i] < prices[i + 1]) {
        profit += prices[i + 1] - prices[i]
      }
    }
    return profit
  };
Copy the code