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

By | 2012 年 12 月 5 日

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;
}
};
```

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

1. zhongyuan

我觉得是顺序扫描找到从0-i 最大的收益保存数组，然后逆序扫描找到最小收益，巧妙的地方就在于逆向最小收益正是i-n之间最大收益，然后divide and conquer，逆序扫描的过程就可以算出最大值，用顺序扫描的最大值减去逆序扫描最小值（负数）。得到两次最大收益。

2. keiutou

感觉还是有点问题吧， 假设第一个最大收益是from i to j, where 0<=i<j<=n-1. 楼主的思路是从从j到n－1 区间找第二大的收益。
如果第二大的收益是再0 到 i之间呢？
eg, 2,3,4,5,1,2,3,4,5,6,7,8,4,5,6 这串数字中最大的收益区间是从1到8，而第二大的收益区间是从2到5。 我测试了楼主的代码返回最大收益是10 而不是11。

1. uniEagle Post author

不是你说的那样。
算法并不是先确定了[0,n-1]的最大,比如[i,j]，然后再去找[j+1,n-1]的最大。

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

所以按照你的思路，其实是这样分的:234512345678|456，找到了局部最大。
而算法其实是这样的：尝试了所有的分割点:
2|34512345678456,
23|4512345678456,
234|512345678456,
2345|12345678456 ，这种分割能找到全局最大。
… 省略 …
23451234567845|6

3. Meiling Zhuang

如果最多的交易次数times是个可变的呢？如果是两次，划分为[0,i-1]和[i,n-1]，此时扫描两次，在代码实现上是写成两段，一段从前往后顺序扫描，一段从后往前逆序扫描，但如果是三次，四次，五次呢，觉得按照这种思路想不清楚诶

1. uniEagle Post author

以三次为例，一个简单的思路是这样的：
划分成[0, i-1]和[i, n-1]两段，在前一段上找一次最大，在后一段上找两次最大（同此题）。
这样是O(n^2)的算法。

4. Jianan

采用楼主的方法的java版本
``` 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; } ```

5. Jianqing

正推一次 反推一次 找出中间的临界点i，若限定为交易三次呢？

1. TK

不考虑效率的话，这个算法的核心想法是枚举两次交易的中间分割点，然后用一次的算法来解。三次的话就枚举三次交易中的两个分割点，分别用一次的算法来解，然后求利润最大的。

这其中再加入一些优化就好了，比如两次就可以像帖子里说的这样优化到O(N)

6. 27g

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

7. Pingback: Hao++

1. zxc

第二次要用逆序的原因是因为把原来数组分成(0,i)(i+1,n)，我们要把这两个数组作为单独的数组来处理，如果第二部分再接着顺序扫，是依赖前i个元素的，如果i+1开始扫，应该也可以，但是时间复杂度就上来了，你想想，应该是吧。

8. felicia

写得太清晰了！ 我是小弱，我转载了一下，注明了出处。谢谢楼主。

1. uniEagle Post author

我也就把Leetcode刷了两遍，这是最系统的刷题了。其它就是零星刷点POJ还有和别人讨论的面试题目而已。

9. Kai

我对动态规划总是理解不好，不知道楼主有没有什么好的建议…

1. uniEagle Post author

我的理解是：
一个问题，用递归的方法去解决的时候，会有许多的子问题被计算很多次。动态规划就是将这些把问题从小往大计算，而且记录下子问题计算后的结果，这样以后需要用到子问题的结论，直接读取结果就好，不用再计算一次。

简单的说，就是用空间换时间。

举个例子：3个碟子的汉诺塔，记1，2，3为三个从小到大的碟子，abc是三根柱子。问题是，把123从a挪到c，那么步骤是：
1 -> c
2 -> b
1 -> b
3 -> c
1 -> a
2 -> c
1 -> c
可以看到，前3行和后三行是同一个子问题：将12从一根柱子挪到另一根。
如果用递归去解，这个子问题会计算两次。这还只是3个碟子的情况，可以想见如果碟子数目一多起来，这种重复计算浪费的计算资源是非常多的。
如果用动态规划，这个子问题就只需要计算一次，但是需要存储空间来记下这个问题的解。这样解决n个碟子的问题，只需要计算以下问题即可：
1个碟子的问题
2个碟子的问题
3个碟子的问题

n个碟子的问题
这样计算每次计算都可以查阅前面计算的结果就好了，不用多次计算。

1. tian

大神呀！请问你当初刷leetcode时候速度怎样啊，我感觉我现在不看答案有些题基本没有思路~~

1. uniEagle Post author

也不定，有时候思路对了很快；但是如果思路不对陷入死胡同了，半天也不定做得出一道题。
那你可能需要强迫自己别去看答案，至少自己从各种角度都实在想不出来了再去看答案。你可以在看答案之前遍历尝试一下各种方法，包括什么二分啊、动归啊、归并啊、回溯啊之类的。

10. daniel

求楼主背景，在哪里高就啊，这些灵感都是咋想到的啊~~~ 太赞！想得我脑子都炸了。。。

1. uniEagle Post author

谢谢来访·
我现在是一个Remote Worker，码农··

11. IntSilence

博主对LeeCode上的题目分析都很犀利，受教了。给你点个赞！

12. EDFWard

1. iverkobe

楼主我问一个很弱的问题~leetcode程序怎么用大数据测用时？谢谢楼主！

1. uniEagle Post author

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

13. Pingback: leetcode刷题笔录-2 | 编程·早晨