算法概论week8 | Leetcode 123. Best Time to Buy and Sell Stock III

题目描述

分析

题目要求只能进行两次交易，且在购买股票之前，要先把已经购买了的股票卖出。

第一次交易时，我们可以用一个变量buy1记录前n天的最小股票价格，用sell1记录前n天能获得的最大利润，这样，在第n天，我们可以知道之前几天哪天的股票最优惠，并在那天买入股票，如果在今天卖出，能获得最大利润，那么就把股票卖出。

第二次交易时(实际上紧跟着第一次交易，在同一天进行)，我们用一个变量buy2记录前n天的最小股票价格，这个价格是当天的股票价格减去截止当天能获得的最大利润，即prices[i] - sell1，再用一个变量sell2记录两次交易能获得的最大利润，同理，如果在第n天卖出可以获得最大利润，那么sell2 就等于 prices[n] - buy2.

这样，我们就得到了两次交易的最大利润sell2。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        int buy1 = prices[0],sell1 = prices[0] - buy1;
        int buy2 = prices[0] - sell1,sell2 = prices[0] - buy2;
        for(int price : prices){
            // 当前最低价，买入
            if ( buy1 > price) buy1 = price;
            // 当前最高利润，卖出
            if ( sell1 < price - buy1) sell1 = price - buy1;
            // 第二次
            // 当前，第一次利润加价格最优惠
            if ( buy2 > price - sell1) buy2 = price - sell1;
            // 当前最高利润，卖出
            if ( sell2 < price - buy2) sell2 = price - buy2;
        }
        return sell2;
    }
};