有限状态机

股票买卖问题

leetcode 121

一次买入一次卖出，并获取最大利润，只要求返回最大利润
只要记录介质目前为止的最低价格，并且计算截至目前为止的最大利润就行

class Solution {
    public static int maxProfit(int[] prices) {
        int[] dp = new int[prices.length + 1];
        int minPrice = Integer.MAX_VALUE;
        for (int i = 1; i <= prices.length; i++) {
            minPrice = Math.min(minPrice, prices[i - 1]);
            dp[i] = Math.max(dp[i - 1], prices[i - 1] - minPrice);
        }
        return dp[prices.length];
    }

}

leetcode 122

允许多次交易，但是不允许同时多笔交易

public class L122_maxProfit2 {
    public static int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length + 1][2];
        dp[0][1]= Integer.MIN_VALUE;
        for (int i = 1; i <= prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i - 1], dp[i - 1][1]);
        }
        return dp[prices.length][0];
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(prices));
    }
}

leetcode 123

允许最多两笔交易

public class L123_maxProfit {
    public static int maxProfit(int[] prices) {
        int buyZero = 0;
        int buyOne = Integer.MIN_VALUE,SellOne = 0;
        int buyTwo = Integer.MIN_VALUE,SellTwo = 0;
        //一共五种状态
        // 0 0次买卖
        // 1 1次买
        // 2 1次卖
        // 3 2次买
        // 4 2次卖
        for (int i = 1; i <= prices.length; i++) {
            buyOne = Math.max(buyOne,buyZero-prices[i-1]);
            SellOne = Math.max(SellOne,buyOne+prices[i-1]);
            buyTwo = Math.max(buyTwo,SellOne-prices[i-1]);
            SellTwo = Math.max(SellTwo,buyTwo+prices[i-1]);
        }
        return SellTwo;
    }

    public static void main(String[] args) {
        int[] prices = {3, 3, 5, 0, 0, 3, 1, 4};
        System.out.println(maxProfit(prices));
    }
}

leetcode 188

class Solution {
     public static int maxProfit(int k, int[] prices) {
        if(prices.length==0)return 0;
        int[][] sell = new int[prices.length + 1][k + 1];
        int[][] buy = new int[prices.length + 1][k + 1];
        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        for (int i = 1; i <= k; i++) {
            buy[0][i] = sell[0][i] = Integer.MIN_VALUE / 2;
        }

        for (int i = 1; i < prices.length; i++) {
            buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            for (int j = 1; j <= k; j++) {
                buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i ]);
                sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
            }

        }

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

leetcode 309

单股票买卖不限制交易次数，带冷冻期

public class L309_maxProfit {
    public static int maxProfit(int[] prices) {
        //f[i][0] 目前持有一只股票的累计最大收益
        //f[i][1] 目前不持有股票，且处于冷冻期的累计最大收益
        //f[i][2] 目前不持有股票，且不处于冷冻期的累计最大收益
        int N = prices.length;
        int[][] f = new int[N + 1][3];
        f[0][0] = -prices[0];
        for (int i = 1; i <= N; i++) {
            //目前持有一只股票，两种来源 上一天持有股票不动，或者来自于非冷冻期的上一天
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i - 1]);
            //目前不持有股票，且处于冷冻期 上一天持有并卖掉
            f[i][1] = f[i - 1][0] + prices[i - 1];
            //目前不持有股票，且不处于冷冻期， 来源上一天非冷冻期，或者上一天冷冻期
            f[i][2] = Math.max(f[i-1][1],f[i-1][2]);
        }

        return Math.max(f[N][1],f[N][2]);
    }

    public static void main(String[] args) {
        int[] prices = {1, 2, 3, 0, 2};
        System.out.println(maxProfit(prices));
    }
}

leetcode 714

不限交易次数，带手续费

public static int maxProfit(int[] prices, int fee) {
        int N = prices.length;
        int[] buy = new int[N + 1];
        int[] sell = new int[N + 1];
        buy[0] = -prices[0];
        for (int i = 1; i <= N; i++) {
            //截止目前持有一只股票的最大收益
            buy[i] = Math.max(buy[i - 1], sell[i - 1] - prices[i - 1]);
            //截止目前不持有股票的累计最大收益
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i - 1] - fee);
        }
        
        return sell[N];
    }