lc 123 Best Time to Buy and Sell Stock III

---

123 Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

DP Accepted

题目要求最多只能交易（买进卖出）两次。所以就可以用sell2[i]表示前i天第二次卖出后手中最多有的钱，buy2[i]表示前i天第二次买入后手中最多有的钱，sell1[i]表示前i天第一次卖出后手中最多有的钱，buy1[i]表示前i天第一次买入后手中最多有的钱，其中，假设一开始手中钱的数量为0。可以得到规律：

sell2[i] = max(sell2[i-1], buy2[i-1]+prices[i]);

buy2[i] = max(buy2[i-1], sell1[i-1]-prices[i]);

sell1[i] = max(sell1[i-1], buy1[i-1]+prices[i]);

buy1[i] = max(buy1[i-1], -prices[i]);

观察可以发现，上述四个变量的值只与前一状态有关，所以可以用单个的变量来代替数组。

class Solution {

public:

    int maxProfit(vector<int>& prices) {

        int sell2 = 0, sell1 = 0, buy2 = numeric_limits<int>::min(), buy1 = numeric_limits<int>::min();

        for (int i = 0; i < prices.size(); i++) {

            sell2 = max(sell2, buy2+prices[i]);

            buy2 = max(buy2, sell1-prices[i]);

            sell1 = max(sell1, buy1+prices[i]);

            buy1 = max(buy1, -prices[i]);

        }

        return sell2;

    }

};