互诺 外贸网站建设,无为县住房和城乡建设局网站,如何网络营销,传奇网页游戏排名题目 给定一个数组#xff0c;它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意#xff1a;你不能同时参与多笔交易#xff08;你必须在再次购买前出售掉之前的股票#xff09;。 示例 1: 输入…题目 给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 示例 1: 输入prices [3,3,5,0,0,3,1,4] 输出6 解释在第 4 天股票价格 0的时候买入在第 6 天股票价格 3的时候卖出这笔交易所能获得利润 3-0 3 。 随后在第 7 天股票价格 1的时候买入在第 8 天 股票价格 4的时候卖出这笔交易所能获得利润 4-1 3 。 示例 2 输入prices [1,2,3,4,5] 输出4 解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。 注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。 因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。 示例 3 输入prices [7,6,4,3,1] 输出0 解释在这个情况下, 没有交易完成, 所以最大利润为 0。 示例 4 输入prices [1] 输出0
解题思路 本题参考代码随想录的解法用dp(n,vector(5,0))表示第i天持有股票的状态每天持有股票有5中状态不操作第一次持有股票第一次不持有股票第二次持有股票第二次不持有股票。可以确定递推公式dp[i][k]max(dp[i-1][1], dp[i-1][k-1]-prices[i]), k1或3. dp[i][k]max(dp[i-1][1], dp[i-1][k-1]prices[i]),k2或4. 最后返回第二次不持有股票的最大利润即为所能获得的最大利润。
实现代码
class Solution {
public:int maxProfit(vectorint prices) {if (prices.size() 0) return 0;vectorvectorint dp(prices.size(), vectorint(5, 0));dp[0][1] -prices[0];dp[0][3] -prices[0];for (int i 1; i prices.size(); i) {dp[i][0] dp[i - 1][0];dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] max(dp[i - 1][2], dp[i - 1][1] prices[i]);dp[i][3] max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i]);}return dp[prices.size() - 1][4];}
};
