# 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:

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 * 10^4$
• $0 <= 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.

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

• Continuous rising trading days: Let the stock prices on this rising trading day be $p_1, p_2, ..., p_n$, Then the first day to buy the last day to sell the largest profit, that is $p_n-p_1$ ; Equivalent to buying and selling every day, that is $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
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)