股市系列有很多題,前兩題 Easy 其實不難,但進入 123. Best Time to Buy and Sell Stock III Hard 領域突然一切都不一樣了。
Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
題目會給定一個標示當天股價的陣列,求在最多兩次的交易中找出最大獲利值。
以下列出三種參考方式,不得不說演算法真的是太神奇了。
[LeetCode] Best Time to Buy and Sell Stock III 买股票的最佳时间之三
DP方式待研究
[Leetcode 123] Best Time to Buy and Sell Stock III
這個比較直觀好懂,就是把一個陣列切成前後兩段,這樣就可以分別求每一段的最大獲利值(回到第一題)
透過由前往後掃描以及由後往前掃描,可以把時間縮短到O(N)
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() < 2) return 0;
vector<int> trans1(prices.size());
vector<int> trans2(prices.size());
int maxProfit = 0;
int minPrices = prices[0];
trans1[0] = 0;
for(int i=1; i<prices.size(); i++){
minPrices = min(minPrices,prices[i]);
trans1[i] = max(trans1[i-1], prices[i]-minPrices);
}
int maxPrices = prices[prices.size()-1];
trans2[prices.size()-1] = 0;
for(int i=prices.size()-2; i>=0; i--){
maxPrices = max(maxPrices, prices[i]);
trans2[i] = max(trans2[i+1], maxPrices - prices[i]);
}
for(int i=0; i<prices.size(); i++)
maxProfit = max(maxProfit, trans1[i] + trans2[i]);
return maxProfit;
}
};
LeetCode 123. Best Time to Buy and Sell Stock III – Python思路總結
這方法就難懂了一點,從栗子推導可以得知
fb=第一次最佳買點/fp=第一次最佳賣點獲利/sb=第二次最佳買點/sp=第二次最佳賣點獲利=最終答案
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() < 2) return 0;
int fb = INT_MAX, fp = 0, sb = INT_MAX, sp = 0;
for(int i=0; i<prices.size(); i++){
fb = min(fb, prices[i]);
fp = max(fp, prices[i] - fb);
sb = min(sb, prices[i] - fp);
sp = max(sp, prices[i] - sb);
}
return sp;
}
};