leecode专题：买卖股票的最佳时机

发表于 更新于 分类于 ， ，

题目：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。注意你不能在买入股票前卖出股票。必须在再次购买前出售掉之前的股票。根据交易次数限定、交易冻结期以及交易费用等，可以有多种变形题。

  1. 121.买卖股票的最佳时机I：只能交易一次
  2. 122.买卖股票的最佳时机II：不限定交易次数
  3. 123.买卖股票的最佳时机III：限定最多只能交易两次
  4. 188.买卖股票的最佳时机IV：限定最多只能交易k次
  5. 309.最佳买卖股票时机含冷冻期：交易冻结期
  6. 714.买卖股票的最佳时机含手续费：交易费用 解题思路：给定数组prices代表每天的股票价格。我们每天能执行的动作有：买入、卖出或者什么都不做三种选择。然而，题目规定必须在再次购买前出售掉之前的股票，因此，我们执行买入动作的时候，手里必须没有股票；执行卖出动作的时候，手里有且仅有一支股票。我们令k为最多交易的次数，i为第i天股票的价格。第i天所能获得的最大收益T分为两种情况：
  • 第i天结束时，手里没有股票。结束时手里没有股票，可能有两种原因：
  1. 第i-1天结束时，手里没有股票，且第i天什么都不做；
  2. 第i-1天结束时，手里有且仅有一支股票，且第i天卖出这支股票。
    取这两种情况的最大值，即为第i天结束时，手里没有股票所能获得的最大收益。
    $$
    T[i][k][0]=max(T[i-1][k][0], T[i-1][k][1]+prices[i])
    $$
  • 第i天结束时，手里有且仅有一支股票。结束时手里有且仅有一支股票，同样可能有两种原因：
  1. 第i-1天结束时，手里有且仅有一支股票，且第i天什么都不做；
  2. 第i-1天结束时，手里没有股票，且第i天买入一支股票。
    取这两种情况的最大值，即为第i天结束时，手里有且仅有一支股票所能获得的最大收益。
    $$
    T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0]-prices[i])
    $$
    注意：买入股票时，可用交易次数发生改变
    初始条件：
    1
    2
    3
    4
    T[-1][k][0] = 0; //第-1天，手里没有股票，收益为0。（或者初始T[0][k][0]=0）
    T[-1][k][1] = INT_MIN; //第-1天，手里有一支股票，收益为INT_MIN。（或者初始T[0][K][1]=-prices[1]）
    T[i][0][0] = 0; // 允许的交易次数为0，手里有没有股票，收益为0。
    T[i][0][1] = INT_MIN; // 允许的交易次数为1，手里有一支股票，收益为INT_MIN。
    思路来源

代码：

  1. 121.买卖股票的最佳时机I
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int maxProfit(vector<int>& prices) {
        int Ti10 = 0;
        int Ti11 = INT_MIN;
        for (int v:prices) {
            Ti10 = max(Ti10, Ti11 + v);
            Ti11 = max(Ti11, -v); // Ti11 = max(Ti11, Ti00-v);  Ti00=0
        }
        return Ti10;
    }
  2. 122.买卖股票的最佳时机II
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int maxProfit(vector<int>& prices) {
        int Ti0 = 0;
        int Ti1 = INT_MIN;
        for (int v:prices) {
            Ti0 = max(Ti0, Ti1+v);
            Ti1 = max(Ti1, Ti0-v); // k=inf，因此k-1=k
        }
        return Ti0;
    }
  3. 123.买卖股票的最佳时机III
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int maxProfit(vector<int>& prices) {
        int k=2; // k=2
        vector<vector<int>> dp(k+1, {0, INT_MIN}); //定义一个k+1的dp数组，dp[0]为初始状态
        for (int v:prices) {
            for (int i=k; i>0; i--) {
                dp[i][0] = max(dp[i][0], dp[i][1]+v);
                dp[i][1] = max(dp[i][1], dp[i-1][0]-v); // 买入时，消耗交易次数
            }
        }
        return dp.back()[0];
    }
  4. 188.买卖股票的最佳时机IV
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    int maxProfit(int k, vector<int>& prices) {
        int len = prices.size(); 
        if (k >= (len >> 1)) { //k为任意次数。在长度为n的prices数组中，最大的收益交易次数为n/2，因此，当k>=n/2时，k的交易次数不限
            int Ti0 = 0;
            int Ti1 = INT_MIN;
            for (int v:prices) {
                Ti0 = max(Ti0, Ti1+v);
                Ti1 = max(Ti1, Ti0-v);
            }
            return Ti0;
        }
        vector<vector<int>> dp(k+1, {0, INT_MIN});
        for (int v:prices) {
            for (int i=k; i>0; i--) {
                dp[i][0] = max(dp[i][0], dp[i][1]+v);
                dp[i][1] = max(dp[i][1], dp[i-1][0]-v);
            }
        }
        return dp.back()[0];
    }
  5. 309.最佳买卖股票时机含冷冻期
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int maxProfit(vector<int>& prices) {
        int cd = 1; //卖出股票之后，要等1天才能再次买入，cooldown(cd) = 1
        int Ti0 = 0;
        int pre_Ti0 = 0;
        queue<int> pre; // 定义一个队列，用于存储每一天手里没有股票的收益
        int Ti1 = INT_MIN;
        for (int v:prices) {
            pre.push(Ti0); // 此时没有股票，放入队列
            Ti0 = max(Ti0, Ti1+v);
            if (pre.size()==cd+1) { // 当队列的长度达到cd+1，即：队首的元素与当前买入操作之间相隔了一天
                pre_Ti0 = pre.front();
                pre.pop();
            }
            Ti1 = max(Ti1, pre_Ti0-v);
        }
        return Ti0;
    }
  6. 714.买卖股票的最佳时机含手续费
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int maxProfit(vector<int>& prices, int fee) {
        int Ti0 = 0;
        int Ti1 = INT_MIN;
        for (int v:prices) {
            Ti0 = max(Ti0, Ti1+v);
            Ti1 = max(Ti1, Ti0-v-fee); // 交易时，减去手续费
        }
        return Ti0;
    }