Leetcode.122 The best time to Buy or sell stocks II

This is the 30th day of my participation in the Wenwen Challenge

Title description:

The original address

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).

The sample a

Input: prices = [7,1,5,3,6,4] Output: 7 Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3.Copy the code

Example 2

Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), this transaction will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the code

Example 3

Input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

prompt

• 
  $1 <= prices.length <= 3 * 10^4$
• 
  $0 <= prices[i] <= 10^4$

Thought analysis

greedy

There is no limit to the number of trades we can make, so if we sell every time it goes up, the profit must be maximized in the end.

The following description is from the big guy who wrote it more clearly, so he just copied it.

• Stock Buying and selling Strategies:

  • Single trading day: set today’s price p1P_1P1, tomorrow’s price p2p_2 P2, then buy today, sell tomorrow can earn p2− P1P2-P_1 P2 − P1 (negative value represents loss).

  • Consecutive rising trading day: let the stock price of this rising trading day be respectively P1, P2… ,pnp_1, p_2, … , p_n p1,p2,… ,pn, then the maximum profit is obtained from buying on the first day and selling on the last day, namely pn− P1p_n-P_1PN − P1. Pn − P1 =(P2 − P1)+(P3 − P2)+… +(pn− PN −1) P_n-P_1 =(P2-P_1)+(P3-P_2)+… + (p_n p_ {}, n – 1) pn – p1 = (p2 – (p1) + (p3 – p2) +… + (pn – pn – 1)

  • Continuous decline trading day: do not buy and sell the biggest gain, that is, will not lose money.

• Algorithm flow:

  • Iterate through the list of stock trading day pricesprice, the strategy is to buy and sell on all rising days (make all the profits) and not buy and sell on all falling days (never lose money).
    1. settempFor the firsti-1Daily buy and noiThe profit earned from daily sales, i.etemp = prices[i] - prices[i - 1] ;
    2. When the profit is positive that daytemp > 0, add profit to total profitprofit; When the profit of0Or if it is negative, it is skipped directly.
    3. When traversal is complete, total profit is returnedprofit.

AC code

class Solution {
    fun maxProfit(prices: IntArray): Int {
        var profit = 0
        for (i in 1 until prices.size) {
            val temp = prices[i] - prices[i - 1]
            if (temp > 0) {
                profit += temp
            }
        }
        return profit
    }
}
Copy the code

conclusion

Done so many simple questions, finally to the dynamic planning and greedy algorithm, before the company’s ranking, the next level is mandatory to master these two algorithms, this problem is done to learn these two algorithms.

In fact, I can see the solution to this problem, and I can write it down, but I can also work it out and then people say this is greedy algorithm, um…

So sometimes you can do it from a practical point of view, and if you do it a lot, a lot of algorithms that sound very advanced may come naturally to you.

This feeling, especially when writing code, is often encountered in the design pattern part, sometimes some code is packaged, and I do not think about what design pattern I want to use in advance, but according to the actual design of the code, and then write more of this code, naturally become some design pattern.

There is no way in the world, but when more people walk, it becomes a way. Lu xun,

reference

State the problem solving

The Best Time to Buy and sell Stocks II (Greed, clear illustration)

Further reading

Dynamic Programming (1)

Violent Search, Greedy Algorithms, dynamic Programming (Java)