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

知识点

动态规划

解题思路

1. 定义buy[i][j]表示在第i天进行第j次买入操作的最大利润，sell[i][j]表示在第i天进行第j次卖出操作的最大利润，其中0 <= i < n，0 <= j <= k。
2. 初始化buy和sell数组。对于第0天，无论进行多少次买入操作，利润都是负数，即buy[0][j]=Integer.MIN_VALUE。对于第0天进行卖出操作，利润为0，即sell[0][j]=0。
3. 遍历数组prices，从第1天开始更新buy和sell数组的值。对于第i天进行第j次买入操作，可以选择在第i-1天没有操作，或者在第i-1天进行了卖出操作后买入。即buy[i][j] = max(buy[i-1][j], sell[i-1][j-1] - prices[i])。对于第i天进行第j次卖出操作，可以选择在第i-1天没有操作，或者在第i-1天进行了买入操作后卖出。即sell[i][j] = max(sell[i-1][j], buy[i-1][j] + prices[i])。
4. 返回sell[n-1][k]作为最终的最大利润，其中n为数组prices的长度。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param prices int整型一维数组
     * @param k int整型
     * @return int整型
     */
    public int maxProfitII (int[] prices, int k) {
        // write code here
        int n = prices.length;
        int[][] buy = new int[n][k + 1];
        int[][] sell = new int[n][k + 1];

        for (int j = 1; j <= k; j++) {
            buy[0][j] = -prices[0];
            sell[0][j] = 0;
        }

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

        return sell[n - 1][k];
    }
}