输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

 public int maxProfit(int prices[]) {
        if (prices.length == 0){
            return 0;
        }
        int min = prices[0];
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            }
            res  = Math.max(prices[i] - min, res);
        }
        return res;
    }

    @Test
    public void test(){
        int[] prices = {7,1,5,3,6,4} ;
        System.out.println(maxProfit(prices));
    }

public int maxProfit(int prices[]) {
    if (prices.length == 0){
        return 0;
    }

    //flag 可以重新买入：true，可以随时买入卖出：false
    boolean flag = false ;
    int min = prices[0]; //买入的最低价格
    int res = 0;
    for (int i = 1; i < prices.length; i++) {
        //已经卖出了， 此时可以买入了，我们要设置当前最低价格
        if (flag){
            min = prices[i];
            flag = false;
            //可以卖出
        }else {
            //如果当前价格比买入的价格还要低或者相等的时候，设置最低买入价格，i继续向前移动
            //我们是要买入，相等的时候，你也不会卖出呀，所以一直到prices[i] 直最后的结果肯定比min大，这样才会
            if (prices[i] <= min) {
                min = prices[i];
            }else {
                //min肯定会有值，如果可以买入，
                // 并且买入价格是按照比第二条的价格高或者相等的时候会截至，因为你想相等了还可以买入呀，
                // 的时候或者是数组最后一个元素的时候，要卖出，否则继续移动i指针
                if ((i != prices.length-1) && (prices[i] > prices[i+1]) || i == prices.length-1){
                    res = res + prices[i] - min;
                    flag = true;
                }
            }
        }
    }
    return res;
}

@Test
public void test(){
    int[] prices = {1,2,3,4,5} ;
    System.out.println(maxProfit(prices));
}

public int maxProfit(int[] prices) {
    if (prices.length == 0 ) {
        return 0;
    }

    // 初始化
    int[][] dp = new int[prices.length][5];
    // 3 状态都还没有发生，因此应该赋值为一个不可能的数
    for (int i = 0; i < prices.length; i++) {
        dp[i][3] = Integer.MIN_VALUE;
    }


    //卖出的时候，相当于是  卖出价格prices[i] - 前一天的价格，我们何不把买入价格，直接就设置为负数呢。然后负数的买入价格每次取最大的，这样得到的真实买入价格就是小的。利润会最大化
    //初始化第一个买入价格price
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; i++) {

        ///dp[i][3]，第i天，第一次买入后手里还有多少钱 = Math.max（假如入上一天前买入后手里的钱dp[i - 1][1]， 当天如果买入股票后手里的钱 -prices[i]）
        //想象空手套白狼，一开始我们手里就没钱，初始钱就是0，，
        // 现在我们是追求利益最大化，谁都想买在低点，买股票肯定是买价格低的。只有买价格低的，后面张了就能挣钱。买在高点，咋地，追涨杀跌呀
        // 买了股票之后手里就变成负数了哦 。比如，前一天价格是3 ，今天价格是5 ，那我们肯定不会买5呀，肯定会买3.买了之后，我们手里的钱就是 -3 。所以是Math.max
        dp[i][1] = Math.max(dp[i - 1][1],  - prices[i]);

        //dp[i][2]（从头到尾） 第i天，第一次卖出后手里还有多少钱 = Math.max(加入上一天卖出股票后手里的钱 dp[i - 1][2],， 上一天前<不一定非得上一天哦>第一次买入股票后手里的钱 dp[i - 1][1] + 股票当天卖出的价格 prices[i])
        dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);

        //dp[i][3] 第i天，（第二次买入后现在手里还有多少钱） =Math.max（加入上一天之前买入后手里的钱dp[i-1][3]， 当天买入手里的钱(第二次) =>  买入（上一天前第一次的盈利dp[i - 1][2]） +  （如果当天买入股票需要的钱 - prices[i]））
        dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);

        //dp[i][4]  第i天，第二次卖出后现在手里还有多少钱 = Math.max（如果上一天卖出手里的钱dp[i - 1][4]，  当天卖出后手里的钱(第二次) =》 上一天前（不一定非得上一天哦）第二次买入股票手里的钱dp[i - 1][3] + 股票当天的价格dp[i - 1][3] + prices[i]）
        dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
    }

    //dp[len - 1][2] 最后的结果是从头到尾至买入一次高的收入。肯定不如价格跌下来，继续买入再卖出一次的收入多。
    //但是也有可能我们就只能买一次，那就是价格不会跌下来（比如1,2,3,4,5）。 这样的结果就是dp[len - 1][2]了
    return Math.max(dp[prices.length - 1][2], dp[prices.length - 1][4]);
}

@Test
public void test(){
    // int[] prices = {3,3,5,0,0,3,1,4} ;
    int[] prices = {1,2,3,4,5} ;

    System.out.println(maxProfit(prices));
}

    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        // f[i][0]: 手上持有股票的最大收益
        // f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
        // f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
        int[][] dp = new int[n][3];

        //第一天只能买入股票
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; ++i) {
            // Math.max （上一天第一次买入股票手里还剩多少钱 ，上一天不在冷冻区并且又在当天买入股票后手里还剩多少钱）
            dp[i][0] = Math.max(dp[i - 1][0] , dp[i - 1][2] - prices[i] );

            //准备进入冷冻区，上一天买入股票后，今天卖出股票后开始进入冷冻期
            dp[i][1] = dp[i - 1][0] + prices[i];

            // 不在冷冻期手里剩多少钱   Math.max （上一天不在冷冻期手里剩多少钱，上一天在冷冻期（那么今天就不是冷冻期）手里还剩多少钱）
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1]);
        }

        //手上不持有股票的时候，手里剩多少钱
        return Math.max(dp[n - 1][1], dp[n - 1][2]);
    }

@Test
public void test() {
    int[] prices = {1, 2, 3, 0, 2};
    System.out.println(maxProfit(prices));
}