买卖股票问题总结

leetcode上买卖股票问题一共有六道题，六道题十分相似，只要掌握一个算法稍作修改就可以都AC掉，现做一个总结。

买卖股票的最佳时机

只能买卖一次

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int buy = -0x3f3f3f3f;
    int sell = 0;
    for(int i=0;i<n;i++){
        buy = max(buy, 0-prices[i]);
        sell = max(sell, prices[i]+buy);
    }
    return sell;
}

买卖股票的最佳时机 II

可以买卖多次

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int buy = -0x3f3f3f3f;
    int sell = 0;
    for(int i=0;i<n;i++){
        buy = max(buy, sell-prices[i]);
        sell = max(sell, prices[i]+buy);
    }
    return sell;
}

买卖股票的最佳时机 III

只能买卖两次

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int buy = -0x3f3f3f3f;
    int sell = 0;
    int buy2 = -0x3f3f3f3f;
    int sell2 = 0;
    for(int i=0;i<n;i++){
        buy = max(buy, 0-prices[i]);
        sell = max(sell, prices[i]+buy);
        buy2 = max(buy2, sell-prices[i]);
        sell2 = max(sell2, prices[i]+buy2);
    }
    return sell2;
}

买卖股票的最佳时机 IV

只能买卖K次

int maxProfit(int k, vector<int>& prices) {
    int n = prices.size();
    int buy[k+1], sell[k+1];
    for(int i=0;i<=k;i++){
        buy[i] = -0x3f3f3f3f;
        sell[i] = 0;
    }
    for(int i=0;i<n;i++){
        for(int j=1;j<=k;j++){
            buy[j] = max(buy[j], sell[j-1]-prices[i]);
            sell[j] = max(sell[j], prices[i]+buy[j]);
        }
    }
    return sell[k];
}

最佳买卖股票时机含冷冻期

有一天冷冻期，卖了之后隔一个天才能再买

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int buy = -0x3f3f3f3f;
    int sell = 0;
    int sell2 = 0;
    for(int i=0;i<n;i++){
        buy = max(buy, sell2-prices[i]);

        sell2 = sell;
        sell = max(sell, prices[i]+buy);
    }
    return sell;
}

买卖股票的最佳时机含手续费

每次买卖需要交手续费fee（同一次买卖只交一次）

int maxProfit(vector<int>& prices, int fee) {
    int n = prices.size();
    int buy = -0x3f3f3f3f;
    int sell = 0;
    for(int i=0;i<n;i++){
        buy = max(buy, sell-prices[i]-fee);
        sell = max(sell, prices[i]+buy);
    }
    return sell;
}