[Leetcode] 123. Best Time to Buy and Sell Stock III

股市系列有很多題，前兩題 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 买股票的最佳时间之三

ＤＰ方式待研究

[Leetcode 123] Best Time to Buy and Sell Stock III

這個比較直觀好懂，就是把一個陣列切成前後兩段，這樣就可以分別求每一段的最大獲利值（回到第一題）
透過由前往後掃描以及由後往前掃描，可以把時間縮短到Ｏ(Ｎ)

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;
    }
};