class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int cur_mini = INT_MAX, max_profit = 0;
        //考虑在第i天卖出，此时的最大利润是我们买入是在[0...i-1]中的最低点买入的。
        //遍历每一天卖出的情况取最大值即可
        for(int i=0; i<prices.size(); i++){
            max_profit = max(max_profit, prices[i]-cur_mini);
            cur_mini = min(cur_mini,prices[i]);
        }
        return max_profit;
    }
};

//动态规划写法
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 只能进行一次交易
        // 每天结束后有两种状态： 1. 持有股票 2. 没交易过(此时肯定是0),不用表示 3. 交易了一次
        int N = prices.size();
        int dp[N][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i=1;i<N;i++){
            dp[i][0] = max(-prices[i],dp[i-1][0]);
            dp[i][1] = max(dp[i-1][0] + prices[i], dp[i-1][1]);
        }
        return dp[N-1][1];
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 任意一天结束时，会有两种可能的状态。
        // 1. 持有股票; 2. 不持有股票
        // dp[i][0]表示第i天交易完后不持有股票的最大利润，dp[i][1]表示第i天交易完后持有股票的最大利润.
        int n = prices.size();
        int dp[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int i=1;i<n;i++){
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 任意一天结束时，会有四种可能的状态。
        // 1. 只进行过一次买操作; 2. 进行了一次交易(一次买和卖); 3. 进行了一次交易并且买了第二次; 4. 完成了两次交易;
        int N = prices.size();
        int dp[N][4];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;
        for(int i=1;i<N;i++){
            dp[i][0] = max(-prices[i], dp[i-1][0]);
            dp[i][1] = max(dp[i-1][0] + prices[i], dp[i-1][1]);
            dp[i][2] = max(dp[i-1][1] - prices[i], dp[i-1][2]);
            dp[i][3] = max(dp[i-1][2] + prices[i], dp[i-1][3]);
        }
        return dp[N-1][3];
    }
};

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        // 因为买卖次数变多，状态无法枚举
        // buy[i][j]第i天结束后并进行了j次交易且持有股票的情况
        // sell[i][j]第i天结束后并进行了j次交易且不持有股票的情况
        int result = 0;
        int N = prices.size();
        int buy[N][k+1];
        int sell[N][k+1];
        for(int j=0;j<=k;j++){
            buy[0][j] = -prices[0];
            sell[0][j] = 0;
        }
        for(int i=1;i<N;i++){
            sell[i][0] = 0;
            buy[i][0] = max(buy[i-1][0],-prices[i]); //这个初始化很讲究
        }
        for(int i=1;i<N;i++){
            for(int j=1;j<=k;j++){
                buy[i][j] = max(sell[i-1][j]-prices[i], buy[i-1][j]);
                sell[i][j] = max(buy[i-1][j-1]+prices[i], sell[i-1][j]);
                result = max(result,sell[i][j]);
            }
        }
        return result;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 每天交易结束时的状态有
        // 0. 持有股票 1. 不持有股票且处于冷冻期 2. 不持有股票且不处于冷冻期
        int N = prices.size();
        int dp[N][3]; 
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        for(int i=1;i<N;i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]);
            dp[i][1] = dp[i-1][0] + prices[i];
            dp[i][2] = max(dp[i-1][2],dp[i-1][1]);
        }
        return max(dp[N-1][1],dp[N-1][2]);
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int N = prices.size();
        int dp[N][2]; //dp[i][0]代表交易完持有股票，dp[i][1]代表交易完不持有股票
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i=1;i<N;i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]-fee);
        }
        return max(dp[N-1][0],dp[N-1][1]);
    }
};