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).
可以买两次。
如果只是两次，确实很好做。两个数组记录该点前最大利润和该点后的最大利润，然后找出利润和最大的点便可。log n。
|
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
32
33
34
35
36
37
38
39
40 |
class
Solution {public: int
maxProfit(vector<int> &prices) { int
n = prices.size(); vector<int> before(n,0); vector<int> after(n,0); for(int
i = 1 ; i < n ;i++) { if(prices[i]-prices[i-1]+before[i-1]>0) before[i]= prices[i]-prices[i-1]+before[i-1]; else before[i] = 0; } for(int
i = n-2 ; i >= 0 ;i--) { if(prices[i+1] -prices[i] + after[i+1] > 0 ) after[i] = prices[i+1] -prices[i] + after[i+1]; else after[i] = 0; } int
max =0; for(int
i = 1; i < n ; i++) { if(before[i]<before[i-1])before[i]=before[i-1]; } for(int
i= n-2;i>=0;i--) { if(after[i]<after[i+1])after[i]=after[i+1]; } for(int
i = 0 ; i < n ; i++) { if(before[i] + after[i] > max) max = before[i] + after[i]; } return
max; }}; |
Best Time to Buy and Sell Stock III,布布扣,bubuko.com
Best Time to Buy and Sell Stock III
原文：http://www.cnblogs.com/pengyu2003/p/3659413.html