leetcode 买卖股票系列 c++

• • • • [121. 买卖股票的最佳时机](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/)
      • [122. 买卖股票的最佳时机 II](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/)
      • [123. 买卖股票的最佳时机 III](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/)
      • [188. 买卖股票的最佳时机 IV](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/)
      • [剑指 Offer 63. 股票的最大利润](https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/)
      • [309. 最佳买卖股票时机含冷冻期](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)
      • [714. 买卖股票的最佳时机含手续费](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)

class Solution {
public:
    int maxProfit(vector& prices) {
        // stack
        int len = prices.size(), ret = 0;
        if (len == 0)   return 0;
        stack sk;
        sk.push(prices[0]);
        for (int i = 1; i < len; ++i) {
            if (sk.top() > prices[i]) {
                sk.pop();
                sk.push(prices[i]);
            } else {
                ret = max(ret, prices[i] - sk.top());
            }
        }
        return ret;
    }
};

class Solution {
public:
    int maxProfit(vector& prices) {
        int ret = 0, min_num = 1e9;
        for (int i = 0; i < prices.size(); ++i) {
            ret = max(ret, prices[i] - min_num);
            min_num = min(prices[i], min_num);
        }
        return ret;
    }
};

class Solution {
public:
    int maxProfit(vector& prices) {
        int len = prices.size();
        int dp[len][2];
        dp[0][0] = 0, dp[0][1] = -prices[0];
        for (int i = 1; i < len; i++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1]);
        }
        return dp[len-1][0];
    }
};

class Solution {
public:
    int maxProfit(vector& prices) {   
        int ans = 0;
        int n = prices.size();
        for (int i = 1; i < n; ++i) {
            ans += max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
};

class Solution {
public:
    int maxProfit(vector& prices) {
        int len = prices.size();
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < len; ++i) {
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);    // 状态转移，第二次购买的代价为第一次卖出的盈利-购买的价格
            sell2 = max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
};

class Solution {
public:
    int maxProfit(int k, vector& prices) {
        if (prices.empty()) {
            return 0;
        }

        int n = prices.size();
        k = min(k, n / 2);
        vector> buy(n, vector(k + 1));
        vector> sell(n, vector(k + 1));

        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        for (int i = 1; i <= k; ++i) {
            buy[0][i] = sell[0][i] = INT_MIN / 2;
        }

        for (int i = 1; i < n; ++i) {
            buy[i][0] = max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            for (int j = 1; j <= k; ++j) {
                buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);   
            }
        }

        return *max_element(sell[n - 1].begin(), sell[n - 1].end());
    }
};

class Solution {
public:
    int maxProfit(vector& prices) {
        int ret = 0;
        stack sk;
        for (int i = 0; i < prices.size(); i++) {
            if (sk.empty()) {
                sk.push(prices[i]);
                continue;
            }
            if (prices[i] >= sk.top()) {
                ret = max(ret, prices[i] - sk.top());
            } else {
                sk.pop();
                sk.push(prices[i]);
            }
        }
        return ret;
    }
};

class Solution {
public:
    int maxProfit(vector& prices) {
        int len = prices.size();
        if (len == 0)   return 0;
        // f[i][0]: 手上持有股票的最大收益
        // f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
        // f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
        vector> dp(len, vector(3));
        dp[0][0] = -prices[0];
        for (int i = 1; i < len; ++i) {
            dp[i][0] = max({dp[i - 1][0], dp[i - 1][2] - prices[i]});
            dp[i][1] = max({dp[i - 1][0] + prices[i], dp[i - 1][1], dp[i - 1][2]});
            dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]);
        }
        return max(dp[len - 1][1], dp[len - 1][2]);
    }
};

class Solution {
public:
    int maxProfit(vector& prices, int fee) {
        int len = prices.size();
        vector buy(len), sell(len);
        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i < len; ++i) {
            buy[i] = max(buy[i - 1], sell[i - 1] - prices[i]);
            sell[i] = max(buy[i - 1] + prices[i] - fee, sell[i - 1]);
        }
        return *max_element(sell.begin(), sell.end());
    }
};

class Solution {
public:
    int maxProfit(vector& prices, int fee) {
        int len = prices.size();
        // buy和sell都只跟前一个前一个状态有关，故优化dp数组
        int buy = -prices[0], sell = 0;
        for (int i = 1; i < len; ++i) {
            buy = max(buy, sell - prices[i]);
            sell = max(buy + prices[i] - fee, sell);
        }
        return sell;
    }
};