問題連結: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
給定一陣列prices, prices[i]代表第i天時的股票價錢
回傳我們可以在這幾天中最多可以賺到多少錢, 限制最多只能做兩次買進買出
限制: 你不能同時在還沒賣掉手上股票前, 又買入另一天的股票 (手上沒股票時才能買股票)
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
我們可以在第四天買入,第六天賣出(賺3); 在第七天買入, 第八天賣出(賺3)。所以總共賺6想法:
這題是121. Best Time to Buy and Sell Stock 和 122. Best Time to Buy and Sell Stock II的變形題, 可以先看這篇文章來幫助你如何解這個問題的簡單版本
這題解法比前兩題都難許多, 我們不能單純的只是找最高營收的兩個交易並回傳他們的和, 因為也有可能這兩個最高營收其實是不能同時存在的
也有可能最大的總和反而是某一次交易的收益
程式邏輯:
雖然接下來所解釋的程式並不是最佳解, 畢竟我還多用了O(n)的空間來做dynamic programming, 但我可以說接下來的程式碼, 也許是你看過最容易懂的寫法, 因為其實只是利用解上述提到過的第 121 題的概念來做變形而已
我們多創了兩個陣列left, right 來存我們到達那天時可以達到的最大利潤
為何會需要兩個陣列則是因為我們
一次是從左到右來找最佳賣出日(已經先用目前最好的價格買股票了 然後再找脫手日),
另一次則是我們從右到左來找最佳買股票的日子(也就是我們是未來人, 已經先決定哪天賣了)
⚠️ 因為我們的程式中的陣列都是從index 0 開始, 下列形容第一天我們將會用Day 0來表示, 以免混淆prices[0]為何指的是Day 1
我們開始講解我們的程式碼邏輯前 先介紹我們在這裡會用到的重要變數們:
- left: 一個陣列, left[i]代表從Day 0到Day i時可得到最大利潤
- right: 一個陣列, right[i]代表從最後一天到Day i時可得到的最大利潤
- minPrice: 到Day i時, 我們目前看到的最低股票價格(也可以說最佳買進價)
- maxPrice:從最後一天到現在Day i時的最高股票價格(也可以說最佳賣出價)
- maxProfit: 我們目前可以拿到的最高價格
(總之想要賺最多就是要看你怎麼買低賣高)
那我們來給一個範例來看我們要怎麼找這些天數中的最高利潤, 假設prices = [3,3,5,0,0,3,1,4].
🚧 先來看我們如何運用left 陣列— 目標就是找到最好的日子賣掉我們手上的股票
🔧Step 0. minPrice 就直接預設為Day 0的價錢 我們假設Day 0就是我們買股票的日子
🔧Step 1. 在Day 0 和 Day 1時, 利潤皆為0 (因為賣出的價錢都跟買入一樣)
🔧Step 2. 在Day 2時, 因為可以賺到比現在最高profit (也就是0)還高的錢, 我們決定賣, 此時最高profit為2
🔧Step 3. 在Day 3時, 因為無法比目前最高利潤還高, 我們決定什麼都不做, 因此目前可得的最高利潤同前日
我們也發現今天創最新低價錢, 因此minPrice更新為今天的價錢,因此之後就會假設Day 3是買入日.
🔧Step 4. 在Day 4時, 什麼都不做 因此目前可得的最高利潤同前日
🔧Step 5. 在Day 5時, 我們發現如果我們今天賣的話可得最高利潤, 因此決定賣!
🔧Step 6. 在Day 6時, 什麼都不做 因此目前可得的最高利潤同前日
🔧Step 7. 在Day 7時, 我們發現如果我們今天賣的話可得最高利潤, 因此決定賣!
完成! 現在我們已知我們從Day0到當天時, 若只允許做一次買進賣出, 我們可得到的最高利潤了😄
🚧再來看我們如何運用right陣列 — 目標就是找到最佳日買股票
🔧Step 0. maxPrice預設為Day 7(最後一天)的股票價錢 假設Day 7就是我們的股票賣出日
🔧Step 1. 在Day 7時, 若我們選擇買股票, 那我們可賺利潤為0
🔧Step 2. 在Day 6時, 選擇買, 因為今天買入的話 可以在Day 7賣出的時候賺$3, 現在最高利潤為$3
🔧Step 3. 在Day 5時,不做任何買入動作 因此目前可得的最高利潤同前日
註: 因為我們是未來人, 我們知道明天買入股票比較划算
🔧Step 4. 在Day 4時決定買, 我們發現今天買(免費!)更划算, 現在最高利潤為$4.
🔧Step 5. 在Day 3時, 不做任何動作, 因此目前可得的最高利潤同前日
🔧Step 6. 在Day2時不做任何動作 因此目前可得的最高利潤同前日
我們也發現股票創新高價錢, 更新maxPrice 並且假設Day 2 為最佳賣出日
🔧Step 7. 在Day 1 及Day 0時, 不做任何動作 因此這兩天可得的最高利潤同前日(Day 2)
完成! 現在我們已知我們從最後一天返回到當天時, 若只允許做一次買進賣出, 我們可得到的最高利潤了 😄
最後一步則就是把left[i]跟right[i]加起來找最大總和, 因為我們被允許最多可做兩次買進賣出
以下為 7ms 程式碼, 贏過30%:
public int maxProfit(int[] prices) {
int n = prices.length;
int[] left = new int[n];
int[] right = new int[n];
int minPrice = prices[0];
int maxProfit = 0;
for(int i=1;i<n;i++)
{
int profit = prices[i]-minPrice;
if(profit<0)
minPrice = prices[i];
else if(profit > maxProfit)
maxProfit = profit;
left[i] = maxProfit;
}
int maxPrice = prices[n-1];//maximum price we can sell
maxProfit = 0;
for(int i=n-2;i>=0;i--)
{
int profit = maxPrice - prices[i];
if(profit<0)
maxPrice = prices[i];
else if(profit > maxProfit)
maxProfit = profit;
right[i] = maxProfit;
}
maxProfit = 0;
for(int i=0;i<n;i++)
maxProfit = Math.max(maxProfit,left[i]+right[i]);
return maxProfit;
}上述程式碼時間複雜度為 O(3n).
我們也可以些微的改程式碼,把最後一個for loop併到倒數第二個迴圈,
時間複雜度進步為 O(2n)
下列為 2ms 程式碼, 贏過99% :
public int maxProfit(int[] prices) {
int n = prices.length;
int[] left = new int[n];
int[] right = new int[n];
int minPrice = prices[0];
int maxProfit = 0;
for(int i=1;i<n;i++)
{
maxProfit = Math.max(maxProfit,prices[i]-minPrice);
if(minPrice>prices[i])
minPrice = prices[i];
left[i] = maxProfit;
}
int maxPrice = prices[n-1];
maxProfit = 0;
int totalMAX = 0;
for(int i=n-1;i>=0;i--)
{
maxProfit = Math.max(maxProfit,maxPrice-prices[i]);
if(maxPrice<prices[i])
maxPrice = prices[i];
right[i] = maxProfit;
totalMAX = Math.max(totalMAX,left[i]+right[i]);
} return totalMAX;
}
