Best Time to Buy and Sell Stock

121. Best Time to Buy and Sell Stock

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

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

S: DP 维护当前的最小值和最大profit即可

    int maxProfit(vector<int>& prices) {
        if(prices.size() < 2) return 0;
        int lowestPrice = prices[0], profit = 0;
        for(int i = 1; i < prices.size(); ++i){
            if(prices[i] < lowestPrice) lowestPrice = prices[i];
            else{
                int currentProfit = prices[i] - lowestPrice;
                if(currentProfit > profit) profit = currentProfit;
            }
        }
        return profit;
    }

122. Best Time to Buy and Sell Stock II

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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

S: greedy
贪心算法，只要每天实现max profits，最终就会得到max profits

    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for(int i = 1; i < prices.size(); ++i){
            profit += max(0, prices[i] - prices[i-1]);
        }
        return profit;
    }

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).

S: DP 左右两边扫描

max_early[i]表示从左到右 0 到 i 个元素完成一次交易可获得的最大收益

max_late[i]表示从右到左n-1 到 i 个元素完成一次交易可获得的做大收益

    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        if(size < 2) return 0;
        int low = prices[0], high = prices[size-1], profit = 0;
        vector<int> max_early(size, 0);
        vector<int> max_late(size, 0);
        for(int i = 1; i < size; ++i){
            if(prices[i] > low) max_early[i] = max(max_early[i-1], prices[i] - low); 
            else{
                low = min(low, prices[i]);
                max_early[i] = max_early[i-1];
            } 
        }
        for(int i = size-2; i >= 0; --i){
            if(prices[i] < high) max_late[i] = max(max_late[i+1], high - prices[i]);
            else{
                high = prices[i];
                max_late[i] = max_late[i+1];
            }
            //这里可直接计算结果不用再开一次循环
            profit = max(profit, max_early[i] + max_late[i]);
        }
        return profit;
    }

88. Best Time to Buy and Sell Stock IV

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 k transactions.

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

S: 二维DP

关键是如何确立state，即要存储的中间值，以及由小到大转换的function。

• buy[i][j]表示在i处已完成了j-1次交易并处在已买入状态时手里的余额，此时第j次交易还没有结束
• sell[i][j]表示在i处已完成了j次交易，手里的余额

对于i,j循环的内循环i是固定的所以可以把二维转化为一维。另外如果k>=size/2实际上可以交易的次数是无限的，可直接用greedy解法。

int maxProfit(int k, vector<int>& prices) {
        int size = prices.size();
        if(size < 2) return 0;
        if(k >= size/2) return greedyProfit(prices);
        vector<int> buy(k+1, INT_MIN);//balance after i txn: have a stock in hand, haven't sold it yet, open to sell.
        vector<int> sell(k+1, 0);//balance after finish i txn: no stock hold in hand, open to buy.
        for(int i = 0; i < size; ++i){
            for(int j = 1; j <= k; ++j){
                //buy[j] = sell[j-1]-prices[i]意为在i处买入，balance减去买入股票价格
                //buy[j] = buy[j] 意味在i处不进行操作，buy[j]维持i-1时的值
                buy[j] = max(sell[j-1] - prices[i], buy[j]);
                //此处应是buy[j]而不是buy[j-1]因为buy[j]的第j次txn没有完成，现在卖出是完成第j次txn
                sell[j] = max(buy[j] + prices[i], sell[j]);
            }
        }
        return sell[k];
    }
    int greedyProfit(vector<int>& prices) {
        int profit = 0;
        for(int i = 1; i < prices.size(); ++i){
            profit += max(0, prices[i] - prices[i-1]);
        }
        return profit;
    }

309. Best Time to Buy and Sell Stock with Cooldown

Say you have an array for which theithelement is the price of a given stock on dayi.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

S: DP O(n)

第i位有三种状态：

buy[i]表示i之前的序列最后一个操作是buy时的最大profit

sell[i]表示i之前的序列最后一个操作是sell时最大profit

rest[i]表示i之前的序列最后一个操作是rest时最大的profit

buy[i] = max(rest[i-1] - price[i-1], buy[i-1]) 在i处买,或什么也不干维持以前的buy状态

sell[i] = max(buy[i-1] + price[i-1], sell[i-1]) 在i处卖,或什么也不干维持以前的sell状态

rest[i] = max(rest[i-1], buy[i-1], sell[i-1]) 不管i以前最后一个操作是什么，i处啥也不干

因为rest一定在sell之后buy之前，所以rest[i] >= buy[i], rest[i] <= sell[i] => rest[i] = sell[i-1]

替换到公式中有 buy[i] = max(sell[i-2] - price[i-1], buy[i-1]) 可用滚动数组优化存储

    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n < 2) return 0;
        vector<int> buy(2, INT_MIN);
        vector<int> sell(3, 0);
        buy[1] = -prices[0];
        for (int i = 2; i <= n; ++i) {
            buy[i % 2] = max(sell[(i - 2) % 3] - prices[i - 1], buy[(i - 1) % 2]);
            sell[i % 3] = max(buy[(i - 1) % 2] + prices[i - 1], sell[(i - 1) % 3]);
        }
        return sell[n % 3];
    }