题解 | #牛群买卖计划#
牛群买卖计划
https://www.nowcoder.com/practice/3e4ae511b4a941b788da5077b08a7d07
考察的知识点:动态规划;
解答方法分析:
- 初始化数组
buy
和sell
的第一行,其中buy[0][0]
表示第一天进行买入的最低价格,sell[0][0]
表示第一天进行卖出的最大利润。 - 使用状态转移方程来更新数组中的每个素。对于第
i
天,需要考虑以下情况:在第i
天买入股票的最低价格:buy[i][j] = max(buy[i-1][j], sell[i-1][j] - prices[i])
,其中j
表示交易次数。 - 在第
i
天卖出股票的最大利润:sell[i][j] = max(sell[i-1][j], buy[i-1][j-1] + prices[i])
。 - 通过遍历
sell
数组的最后一列,找到其中的最大值作为最终的结果。
所用编程语言:C++;
完整编程代码:↓
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param prices int整型vector * @return int整型 */ int maxProfit(vector<int>& prices) { int n = prices.size(); if (n == 0) return 0; vector<vector<int>> buy(n, vector<int>(4, 0)); vector<vector<int>> sell(n, vector<int>(4, 0)); int count = 3; int ans = 0; buy[0][0] = -prices[0]; for (int i = 1; i <= count; i++) buy[0][i] = sell[0][i] = -5000; for (int i = 1; i < n; i++) { buy[i][0] = max(buy[i - 1][0], sell[i - 1][0] - prices[i]); for (int j = 1; j <= count; j++) { buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i]); sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]); ans = max(ans, sell[i][j]); } } return ans; } };