题解 | #牛群买卖计划#

知识点

动态规划

解题思路

1. 定义buy[i][j]表示在第i天进行第j次买入操作的最大利润，sell[i][j]表示在第i天进行第j次卖出操作的最大利润，其中0 <= i < n，0 <= j <= 3。
2. 初始化buy和sell数组。对于第0天，无论进行多少次买入操作，利润都是负数。对于第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][3]作为最终的最大利润，其中n为数组prices的长度。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param prices int整型一维数组
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        int n = prices.length;
    int[][] buy = new int[n][4];
    int[][] sell = new int[n][4];
    
    for (int j = 1; j <= 3; j++) {
        buy[0][j] = -prices[0];
        sell[0][j] = 0;
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= 3; 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][3];
    }
}