Best Time to Buy and Sell Stock

LeetCode

问题一 121

只能买入和卖出一次(1次交易)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        int Min = INT_MAX;
        for(int i = 0; i < prices.size(); ++i) {
            Min = min(prices[i], Min);
            ans = max(ans, prices[i]-Min);
        }
        return ans;
    }
};

问题二 122

任意次交易，直接贪心

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 1; i < prices.size(); ++i) {
            int diff = prices[i] - prices[i-1];
            if (diff > 0) ans += diff;
        }
        return ans;
    }
};

为什么贪心可以work?
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/solution/

问题三 123

at most两个交易，因此是两个区间可以都是闭的，这种情况下相当于是一个交易

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        int n = prices.size();
        int low = prices[0];
        int leftMax[n], rightMax[n];
        leftMax[0] = 0;
        // leftMax是闭区间
        for(int i = 1; i < n; ++i) {
            low = min(low, prices[i]);
            leftMax[i] = max(leftMax[i-1], prices[i] - low);
        }
        rightMax[n-1] = 0;
        int peak = prices[n-1];
        int maxP = rightMax[n-1] + leftMax[n-1];
        for(int i = n-2; i >= 0; --i) {
            peak = max(peak, prices[i]);
            rightMax[i] = max(rightMax[i+1], peak - prices[i]);
            if (leftMax[i] + rightMax[i] > maxP)
                maxP = leftMax[i] + rightMax[i];
        }
        return maxP;
    }
};

问题四 188

at most k transactions.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/135704/Detail-explanation-of-DP-solution

also see to understand better
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/54198/DP-O(KN)-TimeO(n)-Space-cpp-solution.

dp[k, i] = max(dp[k, i-1], prices[i] + max(-prices[j] + dp[k-1, j])), j=[0..i]

class Solution {
public:

    int maxProfit_all(vector<int> &prices) {
        int n = prices.size();
        int sum = 0;
        for(int i = 1;i < n;i++){
            if(prices[i] > prices[i-1]){
                sum += prices[i] - prices[i-1];
            }
        }
        return sum;
    }

    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if(k >= n/2){
            return maxProfit_all(prices);    
        }

        vector<int> Min(k+1, 0);
        vector<int> dp(k+1, 0);
        for(int kk = 0; kk <= k; ++kk) Min[kk] = prices[0];

        for(int i = 1; i < n; ++i) {
            for(int kk = 1; kk <= k; ++kk) {
                //这个dp[kk-1]应该是新的值了，也就是dp[i][kk-1]
                Min[kk] = min(Min[kk], prices[i] - dp[kk-1]);
                dp[kk] = max(dp[kk], prices[i] - Min[kk]);
            }
        }
        return dp[k];
    }
};

另外一种dp解法如下:
更符合通解的思路
dp方程如下: i为prices的Index

buy[i][j] = max(buy[i-1][j], sell[i-1][j-1]-prices[i])
sell[i][j] = max(sell[i-1][j], buy[i-1][j]+prices[i])

// O(kn) O(k)
// 省空间的时候，还是要保证运算结果的正确性
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size() < 2 || k < 1) return 0;
        if (k > prices.size() / 2) return greedy(prices);
        vector<int> buy(k, INT_MIN), sell(k, 0);
        for (auto p : prices) {
            buy[0] = max(buy[0], -p);
            sell[0] = max(sell[0], buy[0] + p);
            for (int i = 1; i < k; i++) {
                int tmp = buy[i];
                buy[i] = max(buy[i], sell[i - 1] - p);
                sell[i] = max(sell[i], tmp + p);
            }
        }
        return sell[k - 1];
    }
private:
    int greedy(vector<int>& prices) {
        int profit = 0;
        for (int i = 1; i < prices.size(); i++) {
            profit += (prices[i] > prices[i - 1]) ? (prices[i] - prices[i - 1]) : 0;
        }
        return profit;
    }
};

问题五 309

可以任意买卖，但是必须有一个冷冻期，如下
[buy, sell, cooldown, buy, sell]

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0) return 0;
        /* buy[i] = Math.max(sell[i-2]-prices[i], buy[i-1])
         * sell[i] = Math.max(sell[i-1], buy[i-1] + prices[i])
         */
        int curBuy = Integer.MIN_VALUE;
        int preSell = 0, curSell = 0;
        for(int price : prices) {
            int tmp = curBuy;
            curBuy = Math.max(preSell - price, curBuy);
            preSell = curSell;
            curSell = Math.max(preSell, tmp + price);
        }

        return curSell;
    }
}

问题六 714

可以进行无限笔交易，但是每笔交易都有费用，要在尽可能少的交易情况下获得最大的收入
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/203709/DP-C%2B%2B-Solution-with-explaination

int maxProfit(vector<int>& prices, int fee) {
    int n = prices.size();
    int dp[n] = {0}; //maximum profit
    int max_prof = dp[0] - prices[0] - fee;

    for(int i = 1; i<n; i++) {
        dp[i] = max(dp[i-1], max_prof + prices[i]); //do nothing or sell
        max_prof = max(max_prof, dp[i] - prices[i] - fee);
    }
    return dp[n-1];
}

另外一种解法:
售出股票时-fee，当然也可以在买入股票时-fee
// buy[i] = max(buy[i-1], sell[i-1] - prices[i])
// sell[i] = max(sell[i-1], buy[i-1] + prices[i] - fee)

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if(prices.size() == 0 or prices.size() == 1){
            return 0;
        }
        int buy = -prices[0];
        int sell = 0;

        for(int i = 1; i < prices.size(); i++){
            int new_buy = max(buy, sell - prices[i]); 
            int new_sell = max(sell, buy + prices[i] - fee);

            buy = new_buy;
            sell = new_sell;
        }

        return sell;  
    }
};

整体框架:
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/most-consistent-ways-of-dealing-with-the-series-of-stock-problems/111012
https://github.com/liyiye012/LeetCode/blob/master/%E8%82%A1%E7%A5%A8%E4%BA%A4%E6%98%93%E9%97%AE%E9%A2%98%E9%80%9A%E8%A7%A3%E5%B0%8F%E7%BB%93