LN : leetcode 123 Best Time to Buy and Sell Stock III

lc 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;
    }
};