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
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).
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 = 51 = 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 = 63 = 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 = 51 = 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.

Stock trading strategy:

Single trading day: set today's price$p_1$ , Tomorrow price $p_2$ , Then buy today and sell tomorrow to earn money $p_2p_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_np_1$ ; Equivalent to buying and selling every day, that is $p_np_1=(p_2p_1)+(p_3p_2)+...+(p_np_{n1})$

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).
 Assume tempFor the firsti1Day buy and firstiThe profit earned from daily selling, namelytemp = prices[i]prices[i1];
 When the profit on that day is positive temp> 0, Then add profit to total profitprofit; When the profit is0Or negative, skip directly;
 After the traversal is complete, return the total profit profit.
 Assume
 Traverse the price list of the entire stock trading day
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
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
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)