Leetcode上有一组《买卖股票的最佳时机》的相关题目，个人感觉比较简单有趣，分享下自己的一点看法。

Ⅰ

问题

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

解答

记录之前的最小price为min_price，记录当前的最大利润为max_profit，遍历一次即可。

时间：O(n)、空间：O(1)

int maxProfit(vector<int>& prices) {
    if(prices.size() < 2) return 0;
    int min_price = prices[0], max_profit = prices[1] - prices[0];
    for (int& price : prices) {
        min_price = min(min_price, price);
        max_profit = max(max_profit, price - min_price);
    }
    return max_profit;
}

Ⅱ

问题

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解答

容易发现当p < m < q时，第p天买入，第q天卖出，等价于第p天买入，第m天卖出，第m天买入，第q天卖出。

即prices[q] - prices[p] = prices[q] - prices[m] + prices[m] - prices[p]。

因此只需要满足相邻的两天能赚钱即可将利益最大化，即prices[i+1] - prices[i] > 0。

时间：O(n)、空间：O(1)

int maxProfit(vector<int>& prices) {
    if (prices.size() < 2) return 0;
    int n = prices.size(), max_profit = 0;
    for (int i = 0; i < n - 1; ++i) {
        max_profit += max(0, prices[i + 1] - prices[i]);
    }
    return max_profit;
}

Ⅲ、Ⅳ

问题

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k （Ⅲ是k=2的情况）笔交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解答

max_profits[i]为完成第i次交易的最大利益，第0次为0。

把后面的成本和前面的最大利益做减法，作为后面的成本，等价于把Ⅰ的算法在循环内执行k次即可。

时间：O(nk)、空间：O(k)

int maxProfit(vector<int>& prices, int k) {
    if (prices.size() < 2) return 0;
    vector<int> min_prices(k, prices[0]);
    vector<int> max_profits(k + 1, 0);
    for (int& price : prices) {
        for (int i = 0; i < k; ++i) {
            min_prices[i] = min(min_prices[i], price - max_profits[i]);
            max_profits[i + 1] = max(max_profits[i + 1], price - min_prices[i]);
        }
    }
    return max_profits[k];
}

含手续费

问题

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，非负整数 fee 代表了交易股票的手续费用。

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

返回获得利润的最大值。

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

解答

possess[i]表示第i天交易后手里有股票最大利润，no_possess[i]表示第i天交易后手里没有股票最大利润。

possess[i] = max(possess[i - 1], no_possess[i - 1] - prices[i])

no_possess[i] = max(no_possess[i - 1], possess[i - 1] + prices[i] - fee)

明显possess[0] = -prices[0]，no_possess[0] = -0

全部交易结束后，持有股票的收益一定低于不持有股票的收益。

时间：O(n)、空间：O(n)

int maxProfit(vector<int>& prices, int fee)
{
    if (prices.size() < 2) return 0;
    int n = prices.size();
    vector<int> possess(n, 0);
    vector<int> no_possess(n, 0);
    possess[0] = -prices[0];
    for (int i = 1; i < n; ++i) {
        possess[i] = max(possess[i - 1], no_possess[i - 1] - prices[i]);
        no_possess[i] = max(no_possess[i - 1], possess[i - 1] + prices[i] - fee);
    }
    return no_possess[n - 1];
}

空间优化

注意到possess[i]、no_possess[i]都只和possess[i-1]、no_possess[i-1]有关，可以只用两个变量代替。

时间：O(n)、空间：O(1)

int maxProfit(vector<int>& prices, int fee)
{
    if (prices.size() < 2) return 0;
    int n = prices.size();
    int possess = -prices[0];
    int no_possess = 0;
    for (int i = 1; i < n; ++i) {
        // 注意不能分开写，因为这样会导致后面的一个计算用到的是i而不是i-1
        std::tie(possess, no_possess) = std::make_pair(
            max(possess, no_possess - prices[i]),
            max(no_possess, possess + prices[i] - fee));
    }
    return no_possess;
}

含冷冻期

问题

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

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

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

解答

possess[i]表示第i天后手里有股票最大利润，freeze[i]表示第i天后手里没有股票且处于冷冻期的最大利润，no_possess[i]表示第i天后手里没有股票且不处于冷冻期最大利润。

possess[i] = max(possess[i - 1], no_possess[i - 1] - prices[i])

freeze[i] = possess[i - 1] + prices[i]

no_possess[i] = max(no_possess[i - 1], freeze[i - 1])

明显possess[0] = -prices[0]，freeze[0] = 0，no_possess[0] = 0

全部交易结束后，明显最大利润为max(no_possess[n - 1], freeze[n - 1])

int maxProfit(vector<int>& prices)
{
    if (prices.size() < 2) return 0;
    int n = prices.size();
    vector<int> possess(n, 0);
    vector<int> freeze(n, 0);
    vector<int> no_possess(n, 0);
    possess[0] = -prices[0];
    for (int i = 1; i < n; ++i) {
        possess[i] = max(possess[i - 1], no_possess[i - 1] - prices[i]);
        freeze[i] = possess[i - 1] + prices[i];
        no_possess[i] = max(no_possess[i - 1], freeze[i-1]);
    }
    return max(no_possess[n - 1], freeze[n - 1]);
}

空间优化

int maxProfit(vector<int>& prices)
{
    if (prices.size() < 2) return 0;
    int n = prices.size();
    int possess = -prices[0];
    int freeze = 0;
    int no_possess = 0;
    for (int i = 1; i < n; ++i) {
        std::tie(possess, freeze, no_possess) = std::make_tuple(
            max(possess, no_possess - prices[i]),
            possess + prices[i],
            max(no_possess, freeze)
        );
    }
    return max(no_possess, freeze);
}