LeetCode.122 The Best Time to Buy and Sell Stocks II

LeetCode.122 The Best Time to Buy and Sell Stocks II

This is the 30th day I participated in the Wenwen Challenge. For details of the event, please see: Wenwen Challenge

Title description:

Original title address

Given an array

prices
,among them 
prices[i]
Is a given stock
i
Price per day.

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

note
: You cannot participate in multiple transactions at the same time (you must sell the previous stocks before buying again).

Example one

Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on the 2nd day (stock price = 1) and sell on the 3rd day (stock price = 5). This exchange can make a profit = 5-1 = 4.   Then, buy on the 4th day (stock price = 3), and sell on the 5th day (stock price = 6). This exchange can make a profit = 6-3 = 3. Copy code

Example two

Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on the 1st day (stock price = 1) and sell on the 5th day (stock price = 5). This exchange can make a profit = 5-1 = 4.   Note that you cannot buy stocks one after another on the first and second days, and then sell them later. Because this is involved in multiple transactions at the same time, you must sell the previous stocks before buying again. Copy code

Example three

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

prompt

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

Thinking analysis

greedy

Because the number of transactions is not limited, if we sell every time we rise, then the final profit must be maximized.

The following description is from the boss. He wrote more clearly, so I just copied it directly.

  • Stock trading strategy:

    • Single trading day: set today's pricep1p_1 , Tomorrow price p2p_2 , Then buy today and sell tomorrow to earn money p2 p1p_2-p_1 (Negative values represent losses).

    • Continuous rising trading days: Let the stock prices on this rising trading day be p1,p2,...,pnp_1, p_2, ..., p_n , Then the first day to buy the last day to sell the largest profit, that is pn p1p_n-p_1 ; Equivalent to buying and selling every day, that is pn p1=(p2 p1)+(p3 p2)+...+(pn pn 1)p_n-p_1=(p_2-p_1)+(p_3-p_2)+...+(p_n-p_{n-1})

    • Consecutive decline trading days: If you do not buy or sell, the profit will be the greatest, that is, you will not lose money.

  • Algorithm flow:

    • Traverse the price list of the entire stock trading day
      price
      , The strategy is to buy and sell on all rising trading days (make all profits), and not to buy on all down trading days (never lose money).
      1. Assume
        temp
        For the first
        i-1
        Day buy and first
        i
        The profit earned from daily selling, namely
        temp = prices[i]-prices[i-1]
        ;
      2. When the profit on that day is positive
        temp> 0
        , Then add profit to total profit
        profit
        ; When the profit is
        0
        Or negative, skip directly;
      3. After the traversal is complete, return the total profit
        profit
        .

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 code

summary

I have done so many simple questions and finally arrived

Dynamic programming
with
how are you
, Before the company evaluated the ranks, the next level had a mandatory requirement to master these two algorithms. This problem is well done to learn these two algorithms.

In fact, I can understand the solution of this question and write it out, but after it is done, others say that this is a greedy algorithm, eh. . .

So sometimes you can still solve problems from actual ideas. If you do a lot, many algorithms that sound very advanced may be natural for you.

This feeling is especially encountered when writing code, the design pattern part is often encountered, sometimes some code is encapsulated, and I did not think in advance what design pattern I would use, but based on the actual design of the code, and then write this code If there are more, it will naturally become certain design patterns.

There is no road in the world, and when there are more people walking, it becomes a road. - Lu Xun

reference

Official problem solving

The best time to buy and sell stocks II (greedy, clear illustration)

Extended reading

Dynamic Planning Essentials (1)

Brute force search, greedy algorithm, dynamic programming (Java)