問題連結: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
問題給予一個陣列prices
prices[i]代表第i天時股票的價格
若我們可以無限次數的買進賣出股票, 求我們可以在這幾天內利用股票最多可以賺多少錢
限制: 你不能同時在還沒賣掉手上股票前, 又買入另一天的股票 (手上沒股票時才能買股票)
範例
Input: [7,1,5,3,6,4]
最多可賺: 7
因為我們在第2天買入第3天買出, 又在第4天買入第5天賣出, 總收益為7想法:
這題是 121. Best Time to Buy and Sell Stock 的變形題
在121題裡, 我們最多只能做一次的買進賣出
因此我們只要一直拿著手上已知天數們的最低價格 去跟目前第i天來做比較,
看可不可以在第i天時造成目前最高效益 (也就是不斷的更新最低價格以及最高效益)
以下為解問題121的程式碼 —
public int maxProfit(int[] prices) {
if(prices==null||prices.length<=1)
return 0;
int min = prices[0];
int maxDiff = 0; //find the maxDiff
for(int i=1;i<prices.length;i++)
{
maxDiff = Math.max(prices[i]-min,maxDiff);
if(prices[i]<min)
min = prices[i];
}
return maxDiff;
}而這題我們則可以做無限次的買進賣出, 最簡單的方法就是只要 當前沒有賠錢, 我們就當作利益可以往上加
public int maxProfit(int[] prices) {
int profit = 0;
for(int i=1;i<prices.length;i++)
{
if(prices[i]>prices[i-1])
profit += prices[i]-prices[i-1];
}
return profit;
}⚠️從程式邏輯你可能會覺得, 這樣不就變成我們很有可能在同天買進賣出, 不太合理 但其實我們並不是真的每次把利益加上去的時候就代表我們在這天"真的賣出"
我們其實是一直不停地把賺錢的差額加進去最終利益而已, 當我們把差額加進我們的最終利益不代表我們真的是那天賣出
比如說 prices=[1,2,3,4,5,3,2,8].
🚧如果用程式邏輯 我們感覺是這樣: 🚧
🔧1'. 第一天買進 第二天賣出 (賺1)
🔧2'. 第二天買進 第三天賣出 (賺1)
🔧3'. 第三天買進 第四天賣出 (賺1)
🔧4'. 第四天買進 第五天賣出 (賺1)
🔧5'. 第五天買進 第六天無法賣 (會賠2)
🔧6'. 第六天買進 第七天無法賣 (會賠1)
🔧7'. 第七天買進 第八天賣出 (賺6)
🚧 但我們真正買進賣出的其實只有兩次: 🚧
🔧1. 在第一天買進, 第五天賣出, 總共賺4 (也就是把上述 1'~4' 全部併在一起, 我們不可能真的在一天買進又一天賣出 這些重疊的日子都會被我們併在一起)
🔧2. 第七天買進 第八天賣出(這個並沒有當天買進賣出的情況發生, 所以不需併入任何東西, 同上述7')
我們真正在做的其實只是把某一個transaction 細細拆解出來, 不停的計算這些連續的利潤, 直到我們不能再幫當前交易繼續壘加更多利益, 才代表我們這個transaction結束!
程式碼時間複雜度O(n), 空間複雜度O(1)
