题解 | #牛群买卖计划II#

动态规划

在每两天之间购入和卖出,并取最大利润,买入前必须卖出

0 <= k <= 100 //交易次数(一次买入卖出)

0 <= prices.length <= 10000 //可供交易的天数

0 <= prices[i] <= 2000 //价格区间

prices.lenght=n天一共可交易n/2次

//故当k>n/2时可以认为,每当相邻的两天可获利时,必然进行了一次买入卖出,此时利润最大

记录每一次买卖后的利润,并挑选最大值记录

可以将利润数组分为买入和卖出数组,计算每一次买入后最大剩余金额(包含之前的利润)+卖出后的金额=利润

则计算sell数组中的最大值即为最大利润(有部分情形下,一次买卖即可达到最大利润)

    public static int maxProfitII(int[] prices, int k) {
        int n = prices.length;
        //当交易次数>一半时，可以认为每天都至少进行了一次买入或卖出操作
        if (k > n / 2) {
            int ans = 0;
            for (int i = 1; i < n; i++) {
                ans += Math.max(0, prices[i] - prices[i - 1]);
            }
            return ans;
        }
        //定义买入后剩余,卖出后利润数组
        int[][] buy = new int[n][k + 1];
        int[][] sell = new int[n][k + 1];
        //第一天购入
        buy[0][0] = -prices[0];
        //卖出
        sell[0][0] = 0;
        //初始化购买后剩余,由于购买后必须卖出才能再次购买
        for (int i = 1; i <= k; i++) {
            buy[0][i] = sell[0][i] = -2001;//,故卖出后最小剩余为0-2000,取余量再-1
        }
        for (int i = 1; i < n; ++i) {
            //在昨天购买或今天购买后取最大剩余
            buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            for (int j = 1; j <= k; ++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]);
            }
        }

        return Arrays.stream(sell[n-1]).max().getAsInt();;
    }