网站系统的设计与实现,网页设计制作网站模板图片,个人中心页面模板,推广普通话的手抄报动态规划
思路#xff1a; 最多可以完成两笔交易#xff0c;因此任意一天结束后#xff0c;会处于5种状态#xff1a; 未进行任何操作#xff1b;只进行了一次买操作#xff1b;进行了一次买操作和一次卖操作#xff1b;再完成了一次交易之后#xff0c;进行了一次买操…动态规划
思路 最多可以完成两笔交易因此任意一天结束后会处于5种状态 未进行任何操作只进行了一次买操作进行了一次买操作和一次卖操作再完成了一次交易之后进行了一次买操作完成了两次交易第 1 种状态利润未发生变化不记录其状态假设其他四种状态的最大利润分别是 buy1sell1buy2sell2对应的状态转移方程 第 i 天状态为 buy1 可以是 第 i - 1 天是 buy1第 i 天不操作即 buy1第 i 天进行买操作第 i - 1 天未进行任何操作 -prices[i]则 buy1 max(buy1, -prices[i])第 i 天状态是 sell1 可以是 第 i - 1 天是 sell1第 i 天不操作即 sell1第 i - 1 天是 buy1第 i 天卖出即 buy1 prices[i]则 sell1 max(sell1, buy1 prices[i])第 i 天状态是 buy2 可以是 第 i - 1 天是 buy2第 i 天不操作即 buy2第 i - 1 天是 sell1第 i 天买入即 sell1 - prices[i]则 buy2 max(buy2, sell1 - prices[i])第 i 天状态是 sell2 可以是 第 i - 1 天是 sell2第 i 天不操作即 sell2第 i - 1 天是 buy2第 i 天卖出即 buy2 prices[i]则 sell2 max(sell2, buy2 prices[i])同一天买入卖出对收益不会产生影响在状态转移时可以直接根据第 i 天计算出的值进行状态转移边界条件第 0 天 buy1 -prices[0]sell1 0buy2 -prices[0]sell2 0从 i 1 开始进行动态规划最终 sell2 的结果即为所求的最大收益
class Solution {
public:int maxProfit(vectorint prices) {int size prices.size();int buy1 -prices[0];int sell1 0;int buy2 -prices[0];int sell2 0;for (int i 0; i size; i) {buy1 std::max(buy1, -prices[i]);sell1 std::max(sell1, buy1 prices[i]);buy2 std::max(buy2, sell1 - prices[i]);sell2 std::max(sell2, buy2 prices[i]);}return sell2;}
};
