题目主要信息:

  • 给出一个数组表示连续多日的股票价格
  • 你可以选择在某一天买入股票,在另一天卖出股票,可以最多买入两次卖出两次,但是第二次买入必须在第一次卖出后,且每天只能进行一次操作
  • 假设买卖没有手续费,问最高收益是多少,即卖出的价格减去买入的价格,如果没有利润需要返回0

具体思路:

这道题与买卖股票的最好时机(一)的区别在于最多可以买入卖出2次,那实际上相当于它的状态多了几个,对于每天有到此为止的最大收益和持股情况两个状态,持股情况有了5种变化,我们用:

  • dp[i][0]dp[i][0]表示到第i天为止没有买过股票的最大收益
  • dp[i][1]dp[i][1]表示到第i天为止买过一次股票还没有卖出的最大收益
  • dp[i][2]dp[i][2]表示到第i天为止买过一次也卖出过一次股票的最大收益
  • dp[i][3]dp[i][3]表示到第i天为止买过两次只卖出过一次股票的最大收益
  • dp[i][4]dp[i][4]表示到第i天为止买过两次同时也买出过两次股票的最大收益

于是使用动态规划,有了如下的状态转移:

  • 初始状态: 与上述提到的题类似,第0天有买入了和没有买两种状态:dp[0][0]=0dp[0][0] = 0dp[0][1]=prices[0]dp[0][1] = -prices[0]
  • 状态转移: 对于后续的每一天,如果当天还是状态0,则与前一天相同,没有区别;如果当天状态为1,可能是之前买过了或者当天才第一次买入,选取较大值:dp[i][1]=max(dp[i1][1],dp[i1][0]prices[i])dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);如果当天状态是2,那必须是在1的状态下(已经买入了一次)当天卖出第一次,或者早在之前就卖出只是还没买入第二次,选取较大值:dp[i][2]=max(dp[i1][2],dp[i1][1]+prices[i])dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);如果当天状态是3,那必须是在2的状态下(已经卖出了第一次)当天买入了第二次,或者早在之前就买入了第二次,只是还没卖出,选取较大值:dp[i][3]=max(dp[i1][3],dp[i1][2]prices[i])dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);如果当天是状态4,那必须是在3的状态下(已经买入了第二次)当天再卖出第二次,或者早在之前就卖出了第二次,选取较大值:dp[i][4]=max(dp[i1][4],dp[i1][3]+prices[i])dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])

alt

最后我们还要从0、第一次卖出、第二次卖出中选取最大值,因为有可能没有收益,也有可能只交易一次收益最大。

ps:因为状态转移的时候,辅助数组只使用到了第i列和第i-1列,因此可以不使用数组,直接用变量代替,优化空间复杂度。

代码实现:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int> > dp(n, vector<int>(5, -10000)); //初始化dp为最小
        dp[0][0] = 0; //第0天不持有状态
        dp[0][1] = -prices[0]; //第0天持有股票
        for(int i = 1; i < n; i++){ //状态转移
            dp[i][0] = dp[i - 1][0]; 
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return max(dp[n - 1][2], max(0, dp[n - 1][4])); //选取最大值,可以只操作一次
    }
};

复杂度分析:

  • 时间复杂度:O(n)O(n),只遍历一次数组
  • 空间复杂度:O(n)O(n),动态规划二维辅助相当于5个一维数组