深圳网站建设最专,wordpress微信h5,网页推广广告,上海做推题目
给定一个数组#xff0c;它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意#xff1a;你不能同时参与多笔交易#xff08;你必须在再次购买前出售掉之前的股票#xff09;。
方法—动态…题目
给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
方法—动态规划
由于我们最多可以完成两笔交易因此在任意一天结束之后我们会处于以下五个状态中的一种 未进行过任何操作利润为0忽略只进行过一次买操作进行了一次买操作和一次卖操作即完成了一笔交易在完成了一笔交易的前提下进行了第二次买操作完成了全部两笔交易。 四种状态的最大利润分别记为 d p 1 , d p 2 , d p 3 , d p 4 dp_1, dp_2, dp_3, dp_4 dp1,dp2,dp3,dp4状态转移 d p 1 m a x ( d p 1 , − p r i c e s [ i ] ) dp_1 max(dp_1, -prices[i]) dp1max(dp1,−prices[i]) # 不做任何操作或者今天买 d p 2 m a x ( d p 2 , d p 1 p r i c e s [ i ] ) dp_2 max(dp_2, dp_1prices[i]) dp2max(dp2,dp1prices[i]) # 不做任何操作或者今天卖 d p 3 m a x ( d p 3 , d p 2 − p r i c e s [ i ] ) dp_3 max(dp_3, dp_2-prices[i]) dp3max(dp3,dp2−prices[i]) # 不做任何操作或者今天买 d p 4 m a x ( d p 4 , d p 3 p r i c e s [ i ] ) dp_4 max(dp_4, dp_3prices[i]) dp4max(dp4,dp3prices[i]) # 不做任何操作或者今天卖 初始状态 d p 1 − p r i c e s [ 0 ] dp_1 -prices[0] dp1−prices[0] # 第一天买入 d p 2 0 dp_2 0 dp20 # 第一天买入并立即卖掉 d p 3 − p r i c e s [ 0 ] dp_3 -prices[0] dp3−prices[0] # 第一支卖了后立即买入第二支 d p 4 0 dp_4 0 dp40 # 立即卖掉第二支
代码
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();int dp1 -prices[0]; // 持有第一支int dp2 0; // 卖或已经卖了第一支int dp3 -prices[0]; // 持有第二支int dp4 0; // 卖或已经卖了第二支int ret 0;for(int i 1; i n; i){dp1 max(dp1, -prices[i]);dp2 max(dp2, prices[i]dp1);dp3 max(dp3, dp2-prices[i]);dp4 max(dp4, prices[i]dp3);}return dp4;}
};
