当前位置:网站首页>Comics: looking for the best time to buy and sell stocks
Comics: looking for the best time to buy and sell stocks
2020-11-08 13:02:00 【I'm sorry.】
Some time ago , Xiaohui released the next two on the stock trading algorithm problem explanation , It has inspired a lot of interest from small partners .
This time, , Xiao Hui integrates these two comics together , And fixed some of the details of the error , Thank you for your advice .
————— the second day —————
What does that mean ? Let's take an example , Given the following array :
The corresponding stock up and down curve of this array is as follows :
obviously , From 2 The price is 1 Buy when , From 5 The price is 8 Sell when , You can get the most out of it :
The biggest payoff at this point is 8-1=7.
In the example above , Maximum 9 At the minimum 1 In front of , How can we trade ? We can't turn back time ?
————————————
The following is an example , If we have set the price 4 It's time to sell , So which is the best time to buy ?
We have to choose the price 4 The previous interval , And must be the minimum value in the interval , obviously , The best choice is price 2 The timing of the .
The first 1 Step , Initialization operation , Put the first 1 Elements as temporary minimum price ; The initial value of maximum return is 0:
The first 2 Step , Traverse to the 2 Elements , because 2<9, So the current minimum price becomes 2; There is no need to calculate the difference ( Because the front element is bigger than it ), The biggest benefit is still 0:
The first 3 Step , Traverse to the 3 Elements , because 7>2, So the current minimum price is still 2; As we said just now , Suppose the price 7 For selling point , The best buy point for that is the price 2, The difference between the two 7-2=5,5>0, So the biggest payoff right now is 5:
The first 4 Step , Traverse to the 4 Elements , because 4>2, So the current minimum price is still 2;4-2=2,2<5, So the biggest payoff is still 5:
The first 5 Step , Traverse to the 5 Elements , because 3>2, So the current minimum price is still 2;3-2=1,1<5, So the biggest payoff is still 5:
And so on , We walk through the end of the array , The minimum price at this time is 1; The biggest benefit is 8-1=7:
public class StockProfit {
public static int maxProfitFor1Time(int prices[]) {
if(prices==null || prices.length==0) {
return 0;
}
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if(prices[i] - minPrice > maxProfit){
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}
public static void main(String[] args) {
int[] prices = {9,2,7,4,3,1,8,4};
System.out.println(maxProfitFor1Time(prices));
}
}
Let's take the array in the following figure for example , Take a visual look at the timing of buying and selling :
In the picture , The green line represents the stage of price rise . Since there is no limit to the number of transactions , So we can buy at every low point , Sell at every high .
thus , All the green parts are our gains , The maximum total return is the sum of these local returns :
(6-1)+(8-3)+(4-2)+(7-4) = 15
As for how to judge these green rising stages ? It's simple , We traverse the entire array , But where the latter is greater than the former , It means that the stock price is in the rising stage .
public int maxProfitForAnyTime(int[] prices) {
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i-1])
maxProfit += prices[i] - prices[i-1];
}
return maxProfit;
}
Let's still take the previous array as an example :
First , Look for 1 The best buy and sell point under the sub limit :
It's impossible to cross the two positions , So we found number one 1 After the second trading position , Take out this pair of buy and sell points and the elements in between :
Next , We follow the same line of thinking , And then look for the rest of the elements 2 The best buy and sell point for sub - Sales :
thus , We found the most 2 The best choice in the case of sub sales :
For the array above , If we solve it twice independently , The best buy and sell points are 【1,9】 and 【6,7】, The biggest benefit is (9-1)+(7-6)=9:
But actually , If you choose 【1,8】 and 【3,9】, The biggest benefit is (8-1)+(9-3)=13>9:
When the first 1 The next best buy and sell point is determined , The first 2 What kind of situation will there be in the position of buying and selling points ?
situation 1: The first 2 Second best buy and sell point , In the 1 Buy sell left
situation 2: The first 2 Second best buy and sell point , In the 1 On the right side of the buying and selling point
situation 3: The first 1 The buy and sell range is cut off from the middle , Split it back into two deals
that , How to judge what kind of situation a given stock price array belongs to ? It's simple , In the 1 After the next maximum buying and selling point is determined , We can compare which situation brings about the largest increase in revenue :
Looking for the biggest gains on the left and right is easy to understand , What's the use of looking for the biggest drop in the middle ?
Think about it and you'll know , When the first 1 When the sale needs to be split up , The biggest drop in the trading range , It's the same as the profit increment after the split ( Similar to the bottom of the stock market operation ):
thus , We can sum up the following formula :
Maximum total revenue = The first 1 The second largest return + Max( The biggest gain on the left , The biggest drop in the middle , The biggest gain on the right )
So called dynamic programming , It is to simplify a complex problem into smaller subproblems , And then from the simple subproblem from the bottom up step by step recursion , Finally, we get the optimal solution of complex problems .
First , Let's analyze the current stock trading problem , This problem requires a certain number of days to be solved 、 The maximum return under a certain number of transactions .
Since the limit on the maximum trading of shares 2 Time , Then the stock transaction can be divided into 5 Stages :
No business
The first 1 Buy... Times
The first 1 Time to sell
The first 2 Buy... Times
The first 2 Time to sell
We set the trading stage of a stock as a variable m( Use from 0 To 4 The value of represents ), Set the range of days as a variable n. And the biggest benefit of our solution is , Influenced by these two variables , It can be expressed as follows :
The biggest gain = F(n,m)(n>=1,0<=m<=4)
Since functions and variables have been determined , Next, we're going to identify two elements of dynamic planning :
1. The initial state of the problem
2. The state transition equation of the problem
What is the initial state of the problem ? We assume that the range of trading days is limited to 1 God , That is to say n=1 The situation of :
1. If there is no business , That is to say m=0 when , The biggest benefit is obviously 0, That is to say F(1,0)= 0
2. If there is 1 Buy... Times , That is to say m=1 when , It's equivalent to subtracting the first one out of thin air 1 Day's share price , The biggest profit is negative day stock price , That is to say F(1,1)= -price[0]
3. If there is 1 Time to buy , That is to say m=2 when , The sale offsets ( Of course , It doesn't make sense ), The biggest benefit is 0, That is to say F(1,2)= 0
4. If there is 2 Buy... Times , That is to say m=3 when , Same as m=1 The situation of ,F(1,3)= -price[0]
5. If there is 2 Time to sell , That is to say m=4 when , Same as m=2 The situation of ,F(1,4)= 0
The initial state is determined , Let's take a look at the state shift . If the range of days is limited from n-1 Days increased to n God , So what happens to the maximum return ?
It depends on what stage is it now ( It's the number of buying and selling ), And for the first time n Day stock price operation ( purchase 、 Sell or wait and see ). Let's analyze the situation at each stage :
1. If there was no sale before , And the first n The sky is still watching , So the biggest payoff is still 0, namely F(n,0) = 0
2. If there was no sale before , And the first n Days to buy , So the biggest return is the negative day stock price , namely F(n,1)= -price[n-1]
3. If there was 1 Buy... Times , And the first n God chooses to wait and see , So the maximum profit is the same as before , namely F(n,1)= F(n-1,1)
4. If there was 1 Buy... Times , And the first n Days to sell , So the biggest payoff is 1 The negative return on the second purchase plus the share price of the day , That is to say F(n,2)= F(n-1,1)+ price[n-1]
5. If there was 1 Time to sell , And the first n God chooses to wait and see , So the maximum profit is the same as before , namely F(n,2)= F(n-1,2)
6. If there was 1 Time to sell , And the first n Days go on 2 Buy... Times , So the biggest payoff is 1 The second sale income minus the share price of the day , namely F(n,3)= F(n-1,2) - price[n-1]
7. If there was 2 Buy... Times , And the first n God chooses to wait and see , So the maximum profit is the same as before , namely F(n,3)= F(n-1,3)
8. If there was 2 Buy... Times , And the first n Days to sell , So the biggest payoff is 2 The second buy income minus the share price of the day , namely F(n,4)= F(n-1,3) + price[n-1]
9. If there was 2 Time to sell , And the first n God chooses to wait and see ( I can only wait and see ), So the maximum profit is the same as before , namely F(n,4)= F(n-1,4)
Last , We put the situation 【2,3】,【4,5】,【6、7】,【8,9】 Merge , It can be summed up as follows 5 An equation :
F(n,0) = 0
F(n,1)= max(-price[n-1],F(n-1,1))
F(n,2)= max(F(n-1,1)+ price[n-1],F(n-1,2))
F(n,3)= max(F(n-1,2)- price[n-1],F(n-1,3))
F(n,4)= max(F(n-1,3)+ price[n-1],F(n-1,4))
From the back 4 In the equation , We can sum up the relationship between the maximum return of each stage and the previous stage :
F(n,m) = max(F(n-1,m-1)+ price[n-1],F(n-1,m))
From this we can conclude that , The complete state transition equation is as follows :
In the table , Different lines represent the maximum return under different day limits , The different columns represent the maximum returns at different stages of trading .
We still use the array from the previous example , Fill in the table on this basis :
First , We fill in the initial state for the table :
Next , We're starting to fill in the 2 Row data .
When there is no business , The maximum benefit must be 0, therefore F(2,0) The result is 0:
According to the previous state transition equation ,F(2,1)= max(F(1,0)-2,F(1,1))= max(-2,-1)= -1, So the first 2 Xing di 2 The result of the column is -1:
F(2,2)= max(F(1,1)+2,F(1,2))= max(1,0)= 1, So the first 2 Xing di 3 The result of the column is 1:
F(2,3)= max(F(1,2)-2,F(1,3))= max(-2,-1)= -1, So the first 2 Xing di 4 The result of the column is -1:
F(2,4)= max(F(1,3)+2,F(1,4))= max(1,0)= 1, So the first 2 Xing di 5 The result of the column is 1:
And then we go on with the state transition equation , Fill first 3 Row data :
Next, fill in the 4 That's ok :
And so on , We've been filling in the entire form :
As shown in the figure , The last data in the table 13, It's the biggest benefit of the whole .
// The maximum number of transactions
private static int MAX_DEAL_TIMES = 2;
public static int maxProfitFor2Time(int[] prices) {
if(prices==null || prices.length==0) {
return 0;
}
// The maximum number of rows in a table
int n = prices.length;
// The maximum number of columns in a table
int m = MAX_DEAL_TIMES*2+1;
// Record data using a two-dimensional array
int[][] resultTable = new int[n][m];
// Fill in the initial state
resultTable[0][1] = -prices[0];
resultTable[0][3] = -prices[0];
// Bottom up , Fill in the data
for(int i=1;i<n;++i) {
for(int j=1;j<m;j++){
if((j&1) == 1){
resultTable[i][j] = Math.max(resultTable[i-1][j], resultTable[i-1][j-1]-prices[i]);
}else {
resultTable[i][j] = Math.max(resultTable[i-1][j], resultTable[i-1][j-1]+prices[i]);
}
}
}
// Return the final result
return resultTable[n-1][m-1];
}
// The maximum number of transactions
private static int MAX_DEAL_TIMES = 2;
public static int maxProfitFor2TimeV2(int[] prices) {
if(prices==null || prices.length==0) {
return 0;
}
// The maximum number of rows in a table
int n = prices.length;
// The maximum number of columns in a table
int m = MAX_DEAL_TIMES*2+1;
// Record data using a one-dimensional array
int[] resultTable = new int[m];
// Fill in the initial state
resultTable[1] = -prices[0];
resultTable[3] = -prices[0];
// Bottom up , Fill in the data
for(int i=1;i<n;++i) {
for(int j=1;j<m;j++){
if((j&1) == 1){
resultTable[j] = Math.max(resultTable[j], resultTable[j-1]-prices[i]);
}else {
resultTable[j] = Math.max(resultTable[j], resultTable[j-1]+prices[i]);
}
}
}
// Return the final result
return resultTable[m-1];
}
In this code ,resultTable From a two-dimensional array to a one-dimensional array . Because the maximum number of transactions is constant , So the spatial complexity of the algorithm also varies from O(n) Down to O(1).
public static int maxProfitForKTime(int[] prices, int k) {
if(prices==null || prices.length==0 || k<=0) {
return 0;
}
// The maximum number of rows in a table
int n = prices.length;
// The maximum number of columns in a table
int m = k*2+1;
// Record data using a one-dimensional array
int[] resultTable = new int[m];
// Fill in the initial state
for(int i=1;i<m;i+=2) {
resultTable[i] = -prices[0];
}
// Bottom up , Fill in the data
for(int i=1;i<n;i++) {
for(int j=1;j<m;j++){
if((j&1) == 1){
resultTable[j] = Math.max(resultTable[j], resultTable[j-1]-prices[i]);
}else {
resultTable[j] = Math.max(resultTable[j], resultTable[j-1]+prices[i]);
}
}
}
// Return the final result
return resultTable[m-1];
}
—————END—————
Friends who like this article , Welcome to the official account Programmer Xiaohui , Watch more
Order one [ Looking at ], It's the biggest support for Xiao Hui !
版权声明
本文为[I'm sorry.]所创,转载请带上原文链接,感谢
边栏推荐
- Python Gadgets: code conversion
- Adobe Lightroom /Lr 2021软件安装包(附安装教程)
- 金融领域首个开源中文BERT预训练模型,熵简科技推出FinBERT 1.0
- Ali tear off the e-commerce label
- How to write a resume and project
- Tight supply! Apple's iPhone 12 power chip capacity exposed
- This time Kwai tiktok is faster than shaking.
- 这次,快手终于比抖音'快'了!
- Written interview questions: find the smallest positive integer missing
- 阿里教你深入浅出玩转物联网平台!(附网盘链接)
猜你喜欢
Introduction to mongodb foundation of distributed document storage database
A scheme to improve the memory utilization of flutter
数据库连接报错之IO异常(The Network Adapter could not establish the connection)
Adobe media encoder / me 2021 software installation package (with installation tutorial)
应届生年薪35w+ !倒挂老员工,互联网大厂薪资为何越来越高?
Major changes in Huawei's cloud: Cloud & AI rises to Huawei's fourth largest BG with full fire
Tencent, which is good at to C, how to take advantage of Tencent's cloud market share in these industries?
笔试面试题目:求缺失的最小正整数
漫画|讲解一下如何写简历&项目
谷歌开源能翻译101种语言的AI模型,只比Facebook多一种
随机推荐
Istio流量管理--Ingress Gateway
Adobe Lightroom / LR 2021 software installation package (with installation tutorial)
金融领域首个开源中文BERT预训练模型,熵简科技推出FinBERT 1.0
Ali tear off the e-commerce label
吐血整理!阿里巴巴 Android 开发手册!(附网盘链接)
数据库连接报错之IO异常(The Network Adapter could not establish the connection)
On the software of express delivery cabinet and deposit cabinet under Windows
阿里云视频云技术专家 LVS 演讲全文:《“云端一体”的智能媒体生产制作演进之路》
一文剖析2020年最火十大物联网应用|IoT Analytics 年度重磅报告出炉!
2035我们将建成这样的国家
笔试面试题目:判断单链表是否有环
Windows下快递投递柜、寄存柜的软件初探
Top 5 Chinese cloud manufacturers in 2018: Alibaba cloud, Tencent cloud, AWS, telecom, Unicom
重返全球第三,小米做对了什么?
2018中国云厂商TOP5:阿里云、腾讯云、AWS、电信、联通 ...
Flink from introduction to Zhenxiang (10. Sink data output elasticsearch)
Flink: from introduction to Zhenxiang (3. Reading data from collection and file)
Ali! Visual computing developer's series of manuals (with internet disk link)
入门级!教你小程序开发不求人(附网盘链接)
Tencent, which is good at to C, how to take advantage of Tencent's cloud market share in these industries?