股市系列有很多題,前兩題 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;
    }
};

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料