题解 | #牛群买卖计划II#
牛群买卖计划II
https://www.nowcoder.com/practice/3fa6bc9c3a724b4089eea26d3f87171b
题目考察的知识点是:
动态规划。
题目解答方法的文字分析:
先判断k是否大于n/2,如果是,则可以进行任意次数的买卖操作,并直接计算所有的正收益之和作为答案。否则,创建两个二维数组buy和sell,分别表示持有股票和卖出股票的最大收益。返回sell数组最后一天的最大收益,即所有交易结束时的最大收益。
本题解析所用的编程语言:
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; 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] = Integer.MIN_VALUE / 2; } 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) { 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]); } } int maxProfit = Integer.MIN_VALUE; for (int profit : sell[n - 1]) { maxProfit = Math.max(maxProfit, profit); } return maxProfit; } }#题解#