[leetcode] 309. Best Time to Buy and Sell Stock with Cooldown

[leetcode] 309. Best Time to Buy and Sell Stock with Cooldown

Description

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day) Example:

Input: [1,2,3,0,2]Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]

分析

题目的意思是： 给你N天股票的价格，设计一个算法求最大利润，并且一次交易完成之后，才能进行下一次交易，另外还加了条件，就是在你卖了之后，还有一天的冷却期，冷却器是不能进行交易的。

推导思路如下：

在第i天买一支股票还能剩下的利润＝第(i-2)天销售能够剩余的利润－第i天股票的价钱．在第i天卖一支股票总的利润＝第(i-1)天买股票剩下的最大利润＋当前股票的价格．也就是说需要维护两个状态的信息，一个是买股票所得到的剩余最大利润，一个是卖出股票之后得到的最大利润，他们互相依赖对方的信息．对于买来说，当天是否买取决于买了之后是否比之前买所剩余的利润大，即状态转移方程为：

buy[i] = max(buy[i-1], sell[i-2] - prices[i-1]);

对于卖来说，同样当天是否将这只股票卖掉取决于卖掉能否获得更大的利润，状态转移方程为： sell[i] = max(sell[i-1], buy[i-1] + prices[i-1]);

本人不擅长dp，这个典型的题目如果做不出来，理解记住一下就行了，以后说不定有用；本人在笔试面试的时候，也没见过这样的dp的题目。

代码

class Solution {public: int maxProfit(vector& prices) { if(prices.size()==0){ return 0; } int len=prices.size(); vector buy(len+1,0),sell(len+1,0); buy[1]=-prices[0]; for(int i=2;i<=len;i++){ buy[i]=max(buy[i-1],sell[i-2]-prices[i-1]); sell[i]=max(sell[i-1],buy[i-1]+prices[i-1]); } return sell[len]; }};

参考文献

​​[leetcode] 309. Best Time to Buy and Sell Stock with Cooldown 解题报告​​​​[LeetCode] Best Time to Buy and Sell Stock with Cooldown 买股票的最佳时间含冷冻期​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。