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).
思考：最多交易两次，设断点分别求前后profit，相加返回最大值，O(n2)超时。原因是重复计算，参考这里，空间换时间。哎，还是思维太局限了，不知变通。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 |
class
Solution {public: int
maxProfit(vector<int> &prices) { int
len=prices.size(); if(len==0||len==1) return
0; vector<int> profit1(len); vector<int> profit2(len); int
i; profit1[0]=0; int
buy=prices[0]; for(i=1;i<len;i++) { buy=min(buy,prices[i]); profit1[i]=max(profit1[i-1],prices[i]-buy); } profit2[len-1]=0; int
sell=prices[len-1]; for(i=len-2;i>=0;i--) { sell=max(sell,prices[i]); profit2[i]=max(profit2[i+1],sell-prices[i]); } int
profit=0; for(i=0;i<len;i++) { if(profit<(profit1[i]+profit2[i])) profit=profit1[i]+profit2[i]; } return
profit; }}; |
[LeetCode]Best Time to Buy and Sell Stock III,布布扣,bubuko.com
[LeetCode]Best Time to Buy and Sell Stock III
原文：http://www.cnblogs.com/Rosanna/p/3591516.html