【动态规划】【数组】【2023-10-03】
有一个表示股票价格的数组,你需要计算出在最多可以完成两笔交易的前提下可获得的最大收益,你必须在再次购买之前卖掉之前的股票。
又是认真学习 买卖股票的最佳时机 III 官方题解的一天
状态
我们在任意的一天交易之后,会有以下五种状态:
转移关系
如果我们知道了第 i-1
天的这四个状态,那么就可以通过第 i-1
天转移到第 i
天,具体地:
i
天可以不进行任何操作,那么这一天的
b
u
y
1
buy_1
buy1 等于前一天的只进行一次买操作获得的最大利润,我们记为
b
u
y
1
′
buy^{'}_1
buy1′;如果在第 i
天只进行了一次买操作,那么这一天的
b
u
y
1
buy_1
buy1 等于前一天的不进行操作获得的最大利润。因此,
b
u
y
1
=
m
a
x
(
b
u
y
1
′
,
−
p
r
i
c
e
s
[
i
]
)
buy_1 = max(buy^{'}_1, -prices[i])
buy1=max(buy1′,−prices[i])。i
天可以不进行任何操作,那么这一天的
s
e
l
l
1
sell_1
sell1 等于前一天的完成了一笔交易获得的最大利润,我们记为
s
e
l
l
1
′
sell^{'}_1
sell1′;如果在第 i
天只进行了一次卖操作,那么这一天的
s
e
l
l
1
sell_1
sell1 等于前一天的进行一次买操作获得的最大利润。因此,
s
e
l
l
1
=
m
a
x
(
s
e
l
l
1
′
,
b
u
y
1
′
−
p
r
i
c
e
s
[
i
]
)
sell_1 = max(sell^{'}_1, buy^{'}_1 - prices[i])
sell1=max(sell1′,buy1′−prices[i])。在考虑边界条件时,我们需要理解下面的这个事实:
无论题目中是否允许「在同一天买入并且卖出」这一操作,最终的答案都不会受到影响,这是因为这一操作带来的收益为零。
因此,最终的状态转移方程为:
{
b
u
y
1
=
max
(
b
u
y
1
,
−
p
r
i
c
e
s
[
i
]
)
s
e
l
l
1
=
max
(
s
e
l
l
1
,
b
u
y
1
+
p
r
i
c
e
s
[
i
]
)
b
u
y
2
=
max
(
b
u
y
2
,
s
e
l
l
1
−
p
r
i
c
e
s
[
i
]
)
s
e
l
l
2
=
max
(
s
e
l
l
2
,
b
u
y
2
+
p
r
i
c
e
s
[
i
]
)
\left\{
base case
那么对于边界条件,我们考虑第 =0
的四个状态:
b
u
y
1
buy_1
buy1 为以
p
r
i
c
e
s
[
0
]
prices[0]
prices[0] 价格买入股票,因此
b
u
y
1
=
p
r
i
c
e
s
[
0
]
buy_1=prices[0]
buy1=prices[0];
s
e
l
l
1
sell_1
sell1 为同一天买入并卖出 ,因此
s
e
l
l
1
=
0
sell_1 = 0
sell1=0;
b
u
y
2
buy_2
buy2 即为在同一天买入并且卖出后再以
p
r
i
c
e
s
[
0
]
prices[0]
prices[0] 的价格买入股票,因此
b
u
y
2
=
−
p
r
i
c
e
s
[
0
]
buy_2=−prices[0]
buy2=−prices[0];同理可得
s
e
l
l
2
=
0
sell_2=0
sell2=0。
最后返回
在动态规划结束后,由于我们可以进行不超过两笔交易,因此最终的答案在 0
,
s
e
l
l
1
sell_1
sell1 和
s
e
l
l
2
sell_2
sell2 中,为三者中的最大值。然而我们可以发现,由于在边界条件中,
s
e
l
l
1
sell_1
sell1 和
s
e
l
l
2
sell_2
sell2 的值已经为 0
,并且在状态转移的过程中我们维护的是最大值,因此
s
e
l
l
1
sell_1
sell1 和
s
e
l
l
2
sell_2
sell2 一定大于等于 0
。同时,如果最优的情况对应的是恰好一笔交易,那么它也会因为我们在转移时允许在同一天买入并且卖出这一宽松的条件,从
s
e
l
l
1
sell_1
sell1 转移至
s
e
l
l
2
sell_2
sell2 ,因此最终的答案即为
s
e
l
l
2
sell_2
sell2。
实现代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int buy1 = -prices[0], sell1 = 0;
int buy2 = -prices[0], sell2 = 0;
for (int i = 1; i < n; ++i) {
buy1 = max(buy1, -prices[i]);
sell1 = max(sell1, buy1 + prices[i]);
buy2= max(buy2, sell1 - prices[i]);
sell2 = max(sell2, buy2 + prices[i]);
}
return sell2;
}
};
复杂度分析
时间复杂度:
O
(
n
)
O(n)
O(n),
n
n
n 为数组 prices
的长度。
空间复杂度: O ( 1 ) O(1) O(1)。
买卖股票系列题目
题目 | 解答 |
---|---|
121. 买卖股票的最佳时机 | 【面试经典150】买卖股票的最佳时机 |
122. 买卖股票的最佳时机 II | 【面试经典150】买卖股票的最佳时机 II |
188. 买卖股票的最佳时机 IV | 【每日一题】买卖股票的最佳时机 IV |
309. 买卖股票的最佳时机含冷冻期 | 【每日一题】买卖股票的最佳时机含冷冻期 |
714. 买卖股票的最佳时机含手续费 | 【每日一题】买卖股票的最佳时机含手续费 |
如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。
最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。