package jjn.carl.dp;
import java.util.Scanner;
/** * @author Jjn * @since 2023/8/23 11:45 */public class LeetCode123 {    public int maxProfit(int[] prices) {        int len = prices.length;        // 边界判断        if (prices.length == 0) return 0;                /*         * 定义 5 种状态:         * dp[i][0]: 没有操作         * dp[i][1]: 第一次买入         * dp[i][2]: 第一次卖出         * dp[i][3]: 第二次买入         * dp[i][4]: 第二次卖出         */        int[][] dp = new int[len][5];        dp[0][1] = -prices[0];        // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润        dp[0][3] = -prices[0];                for (int i = 1; i < len; i++) {            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);        }                return dp[len - 1][4];    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int total = scanner.nextInt();        int[] prices = new int[total];        for (int i = 0; i < total; i++) {            prices[i] = scanner.nextInt();        }        int maxProfit = new LeetCode123().maxProfit(prices);        System.out.println(maxProfit);    }}

package jjn.carl.dp;
import java.util.Scanner;
/** * @author Jjn * @since 2023/8/23 23:18 */public class LeetCode188 {    public int maxProfit(int k, int[] prices) {        if (prices.length == 0) return 0;                int length = prices.length;        int[][][] dp = new int[length][k + 1][2];                // dp数组初始化        // 初始化所有的交易次数是为确保 最后结果是最多 k 次买卖的最大利润        for (int i = 0; i <= k; i++) {            dp[0][i][1] = -prices[0];        }                for (int i = 1; i < length; i++) {            // j 表示交易次数            for (int j = 1; j <= k; j++) {                // dp方程                // dp[i][j][0]表示不持有/卖出,                // dp[i][j][1]表示持有/买入                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);            }        }        return dp[length - 1][k][0];    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int k = scanner.nextInt();        int count = scanner.nextInt();        int[] prices = new int[count];        for (int i = 0; i < count; i++) {            prices[i] = scanner.nextInt();        }        int maxProfit = new LeetCode188().maxProfit(k, prices);        System.out.println(maxProfit);    }}