in LeetCode 算法与数据结构 ~ read.

leetcode 买卖股票系列

买卖股票系列

121.买卖股票的最佳时机[简单]

剑指Offer 63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) { return 0; }
        int max=0;
        // dp[i] 前i天最低价格
        vector<int> dp(prices.size());
        dp[0] = prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            dp[i] = min(dp[i-1], prices[i]);
            max = std::max(prices[i] - dp[i], max);  // 今天为止最低的价格卖出
        }
        return max;
    }
};

122.买卖股票的最佳时机Ⅱ[简单]

给定一个数组 prices ,其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

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

123.买卖股票的最佳时机Ⅲ[困难]

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int none = 0; // 未进行任何操作
        int buy1 = -prices[0];  // 买入过一次
        int sell1= 0;  // 卖出过一次, 当天买入卖出
        int buy2 = -prices[0];  // 买入过二次
        int sell2= 0;  // 卖出过二次,完成全部两次交易
        for (int i = 1; i < prices.size(); ++i) {
            buy1 = std::max(buy1, -prices[i]);
            sell1= std::max(sell1, buy1+prices[i]);
            buy2 = std::max(buy2, sell1-prices[i]);
            sell2= std::max(sell2, buy2+prices[i]);
        }
        return sell2;  // max(none, sell1, sell2)
    }
};

188.买卖股票的最佳时机Ⅳ[困难]

给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

// buy[i][j]  前i天进行j笔交易,持有一支股票的收益
// sell[i][j] 前i天进行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])
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.empty()) { return 0; }
        int n = prices.size();
        k = std::min(k, n/2);  // n天最多交易n/2笔,可忽略
        vector<vector<int>> buy(n, vector<int>(k+1));  // n天k笔交易,持有股票,最大收益
        vector<vector<int>> sell(n, vector<int>(k+1));  // n天k笔交易,不持有股票,最大收益
        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        for (int i = 1; i < k+1; ++i) {
            buy[0][i] = sell[0][i] = INT_MIN/2;  // 第0天 无法交易k笔,初始值设为无效,极小值
        }

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

309.买卖股票的最佳时机含冷冻期[中等]

给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 1) { return 0; }
        
        vector<vector<int>> dp(prices.size(), vector<int>(3));
        dp[0][0] = 0-prices[0];  // 0 买入
        dp[0][1] = 0;            // 1 卖出
        dp[0][2] = 0;            // 2 冷冻
        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = std::max(dp[i-1][2]-prices[i], dp[i-1][0]);
            dp[i][1] = dp[i-1][0]+prices[i];
            dp[i][2] = std::max(dp[i-1][1], dp[i-1][2]);
        }
        return std::max(dp[prices.size()-1][1], dp[prices.size()-1][2]);
    }
};

714.买卖股票的最佳时机含手续费[中等]

给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。

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