# LeetCode题目：Best Time to Buy and Sell Stock III，一维动态规划

Best Time to Buy and Sell Stock III
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 (ie, you must sell the stock before you buy again).

```class Solution {
public:
int maxProfit(vector &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(prices.size() <= 1)
return 0;

//stores the max profit in [0, ... , i] subarray in prices
vector maxEndWith;
{//build the maxEndWith.
int lowest = prices[0];
int maxprofit = 0;
maxEndWith.push_back(0);
for(int i = 1; i < prices.size(); ++i) {
int profit = prices[i] - lowest;
if(profit > maxprofit) {
maxprofit = profit;
}
maxEndWith.push_back(maxprofit);
if(prices[i] < lowest) lowest = prices[i];
}
}

int ret = maxEndWith[prices.size() - 1];
{//reverse to see what is the maxprofit of [i, ... , n-1] subarray in prices
//and meanwhile calculate the final result
int highest = prices[prices.size() - 1];
int maxprofit = 0;
for(int i = prices.size() - 2; i >= 0; --i) {
int profit = highest - prices[i];
if(profit > maxprofit)  maxprofit = profit;
int finalprofit = maxprofit + maxEndWith[i];
if(finalprofit > ret) ret = finalprofit;
if(prices[i] > highest) highest = prices[i];
}
}

return ret;
}
};
```

## “LeetCode题目：Best Time to Buy and Sell Stock III，一维动态规划”上的46条回复

zhongyuan说：

keiutou说：

eg, 2,3,4,5,1,2,3,4,5,6,7,8,4,5,6 这串数字中最大的收益区间是从1到8，而第二大的收益区间是从2到5。 我测试了楼主的代码返回最大收益是10 而不是11。

Max( MaxProfitOn[0,i] + MaxProfitOn[i+1, n-1] )这样的。是把整个数组分两段，分别找最大，看看他们的和在如何分的时候才能达到全局最大。

2|34512345678456,
23|4512345678456,
234|512345678456,
2345|12345678456 ，这种分割能找到全局最大。
… 省略 …
23451234567845|6

Meiling Zhuang说：

Jianan说：

``` public int maxProfit(int[] prices) { if (prices.length <= 1) return 0; int[]D = new int[prices.length]; int min = prices[0]; for (int i = 1; i < prices.length; i++) { if (prices[i] =0; i--) { if (prices[i] > high) high = prices[i]; max = Math.max(max, high-prices[i]+D[i]); } return max; } ```

Jianqing说：

TK说：

fishzhao说：

27g说：

int ret = maxEndWith[prices.size() – 1];应该是 int ret = maxEndWith[maxEndWith.size() – 1];不过不影响，越界也是0

Rachel说：

wow, 这个方法太巧妙了～ 感谢楼主！

yd116说：

Yixing Jiang说：

[…] III: You may complete at most two transactions, but you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). 第三题必须要读清题，题目说是最多可以完成两笔交易，就是说买入2次卖出2次，并且买第2次之前必须卖掉第一次买的（我一开始还想复杂了，忽略了这个条件）。 既然买入第二次之前必须卖掉第一次买的，那么实际上问题就变成了我需要找到一个i，使得0到i天内那笔交易的最大收益与i到n-1天内那笔交易的最大收益之和最大。这样的话每个单独区间的最大收益在问题I中就已经解决了。接下来就需要考虑效率问题，这里有个神奇的地方是参考别人来的(link) […]

[…] III: You may complete at most two transactions, but you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). 第三题必须要读清题，题目说是最多可以完成两笔交易，就是说买入2次卖出2次，并且买第2次之前必须卖掉第一次买的（我一开始还想复杂了，忽略了这个条件）。 既然买入第二次之前必须卖掉第一次买的，那么实际上问题就变成了我需要找到一个i，使得0到i天内那笔交易的最大收益与i到n-1天内那笔交易的最大收益之和最大。这样的话每个单独区间的最大收益在问题I中就已经解决了。接下来就需要考虑效率问题，这里有个神奇的地方是参考别人来的(link) […]

Cool说：

zxc说：

felicia说：

🙂 欢迎来访·

ramboww说：

Kai说：

1 -> c
2 -> b
1 -> b
3 -> c
1 -> a
2 -> c
1 -> c

1个碟子的问题
2个碟子的问题
3个碟子的问题

n个碟子的问题

tian说：

daniel说：

IntSilence说：

：） 谢谢来访，一起学习！

Yong WEN说：

iverkobe说：

Leetcode在改版之前，可以自己选择用小数据集合或者大数据集合测试，改版之后木有了。

[…] 思路：一开始的想法是，把10中的代码拿过来稍作修改，然后将数组分割成[0…i]和[i…n-1]两个部分，最大收益就是两个部分最大收益之和（每个部分进行一次交易）。遍历 i 找出最大的。但是这样太耗时间了，后来看到uniEagle提供的思路，才恍然大悟。其实10中找出一段时间[i…j]内最大收益的过程就已经解决了[i…k]的子问题，只要维护两个一维数组，一个记录[0…i]的最大收益，一个记录[i…n-1]的最大收益即可。这两个数组都是可以在一次遍历中得出的。然后再考虑两个部分收益之和。 […]

Lingyong Wang说：