题目描述

假定你知道某只股票每一天价格的变动。
你最多可以同时持有一只股票。但你最多只能进行两次交易（一次买进和一次卖出记为一次交易。买进和卖出均无手续费）。
请设计一个函数，计算你所能获得的最大收益。

方法一 分而治之

解题思路

要计算两次交易的最大收益，可以把问题分为两部分。找到第k天，求得前k天一次交易的最大收益加上第k天之后一次交易的最大收益。
对于一次交易问题，这里直接给出一次遍历的方法。

如上图所示，我们期望在前k天或者k天之后的历史最低点买入股票，用一个变量记录历史最低价格minprice，我们应该以此价格买入股票。然后遍历数组，在第i天买出股票的利润为prices[i] - minprice。因此，只需要遍历价格数组一遍，记录并更新历史最低点minprice，计算当天卖出的利润，并得到最大值。
需要遍历所有的k来确定两次交易所能得到的最大值，不进行优化的话，每一个k要遍历一次数组，故时间复杂度为。可以使用两个辅助数组记录前k天和k天之后一次交易的最大收益，然后求得二者之和的最大值，这样可以把时间复杂度降低到。

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // 记录最低价格
        int min_price = prices[0];
        // 记录前k天一次交易最大收益
        vector<int> pre(n, 0);
        // 根据题解所言，得到前k天一次交易的最大收益
        for (int i = 1; i < n; ++i)
        {
            min_price = min(min_price, prices[i]);
            pre[i] = max(pre[i - 1], prices[i] - min_price);
        }

        // 记录k天之后一次交易的最大收益
        vector<int> post(n, 0);
        // 记录最高价格
        int max_price = prices[n - 1];
        // 得到k天之后一次交易的最大收益
        for (int i = n - 2; i >= 0; --i)
        {
            max_price = max(max_price, prices[i]);
            post[i] = max(post[i + 1], max_price - prices[i]);
        }

        // 得到两次交易收益和的最大值
        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans = max(ans, pre[i] + post[i]);
        return ans;
    }
};

复杂度分析

• 时间复杂度：进行三次遍历，时间复杂度为
• 空间复杂度：需要两个辅助数组进行记录，空间复杂度为

方法二 动态规划

解题思路

如果只进行一次买卖相比，进行两次买卖的状态变多，用数组表示第i天状态为j时的最大收益。规定状态如下

• ：第i天，第一次未购买
• ：第i天，第一次购买未卖出
• ：第i天，第一次卖出，第二次未购买
• ：第i天，第二次购买未卖出
• ：第i天，第二次卖出

初始化条件为：

相应的状态转移为：

• ，表示第i天无操作
• ，第一项表示第i天无操作，第二项表示第i天买入了股票
• ，第一项表示第i天无操作，第二项表示第i天卖出了股票
• ，第一项表示第i天无操作，第二项表示第i天买入了股票
• ，第一项表示第i天无操作，第二项表示第i天卖出了股票

可以看出，只与相关，所以可以对动态规划数组进行压缩，将其压缩成一维以节约空间。

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // 边界条件
        if (prices.size() == 0)
            return 0;
        int n = prices.size();
        // 5个状态分别为：0 不操作；1 第一次购买；2 第一次卖出；3 第二次购买；4 第二次卖出
        int f[5]={0};
        // 初始化状态
        f[1] = -1 * prices[0];
        f[3] = -1 * prices[0];
        for (int i = 1; i < n; i++) {
            // 对每一天的动态规划数组进行更新
            // 未操作
            // f[0] = f[0];
            // 未操作或买入
            f[1] = max(f[1], f[0] - prices[i]);
            // 未操作或卖出
            f[2] = max(f[2], f[1] + prices[i]);
            // 未操作或买入
            f[3] = max(f[3], f[2] - prices[i]);
            // 未操作或卖出
            f[4] = max(f[4], f[3] + prices[i]);
        }
        return f[4];
    }
};

复杂度分析

• 时间复杂度：只需要遍历一次数组，时间复杂度为
• 空间复杂度：dp数组大小为常数，空间复杂度为