買賣股票系列
【leetcode】40-best-time-to-buy-and-sell-stock 力扣 121. 買賣股票的最佳時(shí)機(jī)
【leetcode】41-best-time-to-buy-and-sell-stock-ii 力扣 122. 買賣股票的最佳時(shí)機(jī) II
【leetcode】42-best-time-to-buy-and-sell-stock-iii 力扣 123. 買賣股票的最佳時(shí)機(jī) III
【leetcode】43-best-time-to-buy-and-sell-stock-iv 力扣 188. 買賣股票的最佳時(shí)機(jī) IV
【leetcode】44-best-time-to-buy-and-sell-stock-with-cooldown 力扣 309. 買賣股票的最佳時(shí)機(jī)包含冷凍期
【leetcode】45-best-time-to-buy-and-sell-stock-with-cooldown 力扣 714. 買賣股票的最佳時(shí)機(jī)包含手續(xù)費(fèi)
開源地址
為了便于大家學(xué)習(xí)儡蔓，所有實(shí)現(xiàn)均已開源。歡迎 fork + star~
力扣 123. 買賣股票的最佳時(shí)機(jī) III
給定一個(gè)數(shù)組尝哆，它的第 i 個(gè)元素是一支給定的股票在第 i 天的價(jià)格印衔。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你最多可以完成 兩筆 交易。
注意：你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）之剧。
示例 1:
輸入：prices = [3,3,5,0,0,3,1,4]
輸出：6
解釋：在第 4 天（股票價(jià)格 = 0）的時(shí)候買入词疼，在第 6 天（股票價(jià)格 = 3）的時(shí)候賣出，這筆交易所能獲得利潤 = 3-0 = 3 赊窥。
隨后熄阻，在第 7 天（股票價(jià)格 = 1）的時(shí)候買入鳄袍，在第 8 天 （股票價(jià)格 = 4）的時(shí)候賣出，這筆交易所能獲得利潤 = 4-1 = 3 盏筐。
示例 2：
輸入：prices = [1,2,3,4,5]
輸出：4
解釋：在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 平绩。
注意你不能在第 1 天和第 2 天接連購買股票纬傲，之后再將它們賣出净嘀。
因?yàn)檫@樣屬于同時(shí)參與了多筆交易稍走，你必須在再次購買前出售掉之前的股票焙压。
示例 3：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這個(gè)情況下, 沒有交易完成, 所以最大利潤為 0。
示例 4：
輸入：prices = [1]
輸出：0
提示：
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^5
v1-思路
借助第一題的思路
我們把整個(gè)交易鏈路拆分為2個(gè)數(shù)組绰沥，在 i 的位置喘垂，拆分為 2 個(gè)數(shù)組。
偽代碼
i = 0 .... n-1
拆分為兩個(gè)數(shù)組：
- 0 ... i 計(jì)算一個(gè)最大值
2）i ... n 計(jì)算一個(gè)最大值
把每一個(gè)位置的兩個(gè)值加起來兜喻，然后計(jì)算保存 max[i]。找到最大值
這個(gè)是廢棄的方案伪货，可以考慮實(shí)現(xiàn)驗(yàn)證一下。
v2-T121 的思路拓展
T121 的解法
這里只是一次的最大值凝垛，計(jì)算思路就是找到最小值 + 最大值捧毛。
public int maxProfit(int[] prices) {
int maxResult = 0;
int minVal = prices[0];
for(int i = 0; i < prices.length; i++) {
minVal = Math.min(minVal, prices[i]);
maxResult = Math.max(prices[i] - minVal, maxResult);
}
return maxResult;
}
代碼
思路：
1）in1_out1_max 記錄的是第一次交易結(jié)束的最大值 b1+s1
2）in1_out1_in2_max 記錄的第一次交易結(jié)束+第二次買入的最大值 b1+s1+b2
2）in1_out1_in2_max+prices[i] 這個(gè)就是完整的交易最大值 b1+s1+b2+s2
public int maxProfit(int[] prices) {
int maxProfit = 0;
// 最小值
int min = prices[0];
int in1_out1_max = 0;
// 買1賣1買2
int in1_out1_in2_max = 0;
for(int i = 0; i < prices.length; i++) {
// 計(jì)算出當(dāng)前的結(jié)果
maxProfit = Math.max(maxProfit, in1_out1_in2_max+prices[i]);
min = Math.min(prices[i], min);
// 第一題的思路而账，記錄最大值
in1_out1_max = Math.max(prices[i] - min, in1_out1_max);
// 下一次的操作
// 去掉當(dāng)前這一次的金額咐吼，準(zhǔn)備好對應(yīng)的金額
in1_out1_in2_max = Math.max(in1_out1_in2_max, in1_out1_max - prices[i]);
}
return maxProfit;
}
V3-dp 解法貫穿思路
思路
其實(shí)整體就是貫穿的 dp 解法撇吞。
2次交易分為2次：
b1 第一次買入
s1 第一次賣出
b2 第二次買入
s2 第二次賣出
初始化
b1, b2 初始化為 -prices[0]
代碼
public int maxProfit(int[] prices) {
int b1 = -prices[0];
int b2 = -prices[0];
int s1 = 0;
int s2 = 0;
for(int i = 0; i < prices.length; i++) {
// 賣出第二筆 是否賣？
s2 = Math.max(s2, b2 + prices[i]);
// 買入第二筆 是否買隆嗅？
b2 = Math.max(b2, s1 - prices[i]);
// 賣出第一筆 是否賣泡躯？
s1 = Math.max(s1, b1 + prices[i]);
// 買入第一筆 是否買？
b1 = Math.max(b1, - prices[i]);
}
return s2;
}
評價(jià)
這一種解法其實(shí)非常容易理解丽焊，也非常容易拓展较剃。
小結(jié)
完整的思路，其實(shí) V2 是一個(gè)比較完整的解法技健。
參考資料
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
