题解 | #牛群买卖计划#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
       public int maxProfit (int[] prices) {
        int n = prices.length;
        int[][][] f = new int[n + 1][4][2];
        for (int i = 0; i <= 3; ++i) {
            f[0][i][1] = Integer.MIN_VALUE;
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= 3; ++j) {
                f[i][j][0] = Math.max(f[i - 1][j][0], f[i - 1][j][1] + prices[i - 1]);
                f[i][j][1] = Math.max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i - 1]);
            }
        }

        return f[n][3][0];
    }
}

本题知识点分析：

1.动态规划

2.数组遍历

3.数学模拟

本题解题思路分析：

1.初始化dp数组，4表示最多3次交易，2表示存在持有股票和不持有股票两种状态

2、将第0天的值设置为Integet.MinValue

3.开始从第一天开始遍历

4.持有股票：前一天最大利润和前一次交易结束不持有股票的最大利润-当天价格，取max

5.不持有股票：max(前一天不持有股票的最大利润,前一天持有股票+当前股市价格)

本题使用编程语言: Java