[leetcode] 123. Best Time to Buy and Sell Stock III

[leetcode] 123. Best Time to Buy and Sell Stock III

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 at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [3,3,5,0,0,3,1,4]Output: 6Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: [1,2,3,4,5]Output: 4Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]Output: 0Explanation: In this case, no transaction is done, i.e. max profit = 0.

分析一

题目的意思为： 设计一个算法求股票的最大收益，要求交易不能超过2次，在做下一个交易前，当前的交易必须完毕。 想法： 这是leetcode的一道hard难度的题目，已经超出了本人的能力了，我这里稍稍充当了一下搬运工，欢迎大牛批评指正。

这里我们先解释最多可以进行k次交易的算法，然后最多进行两次我们只需要把k取成2即可。我们还是使用“局部最优和全局最优解法”。我们维护两种量，一个是当前到达第i天可以最多进行j次交易，最好的利润是多少（global[i][j]），另一个是当前到达第i天，最多可进行j次交易，并且最后一次交易在当天卖出的最好的利润是多少（local[i][j]）。下面我们来看递推式，全局的比较简单，global[i][j]=max(local[i][j],global[i-1][j])，也就是去当前局部最好的，和过往全局最好的中大的那个（因为最后一次交易如果包含当前天一定在局部最好的里面，否则一定在过往全局最优的里面）。对于局部变量的维护，递推式是local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)，也就是看两个量，第一个是全局到i-1天进行j-1次交易，然后加上今天的交易，如果今天是赚钱的话（也就是前面只要j-1次交易，最后一次交易取当前天），第二个量则是取local第i-1天j次交易，然后加上今天的差值（这里因为local[i-1][j]比如包含第i-1天卖出的交易，所以现在变成第i天卖出，并不会增加交易次数，而且这里无论diff是不是大于0都一定要加上，因为否则就不满足local[i][j]必须在最后一天卖出的条件了）。

代码一

class Solution {public: int maxProfit(vector& prices) { if(prices.empty()){ return 0; } int n=prices.size(); int g[n][3]={0}; int l[n][3]={0}; for(int i=1;i

分析二

按照参考博客的思路，buy1记录的是所有天最便宜的报价，sell1记录的是所有天只进行1次买卖的最大利益；buy2表示在第一次获得最大利益后，再买到那次交易后最便宜股价是剩余的净利润，sell2记录的是两次完整交易的最大利润。

代码二

class Solution {public: int maxProfit(vector &prices) { int buy1=INT_MIN; int sell1=0; int buy2=INT_MIN; int sell2=0; for(int i=0;i

参考文献

​​[编程题]best-time-to-buy-and-sell-stock-iii​​​​[LeetCode] Best Time to Buy and Sell Stock III 买股票的最佳时间之三​​​​Best Time to Buy and Sell Stock III – LeetCode​​

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