The third problem in the Best Time to Buy and Sell Stock series. The previous two problems allow unlimited transactions and only one transaction, respectively.
This problem allows two transactions.
With two transactions, you can split the problem at some point, turning it into two single-transaction problems. But this approach times out with O(n^2) complexity.
An alternative approach:
Process forward and backward using the single-transaction method, then store the max value at each point. This gives a linear solution.
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| class Solution {
public:
int maxProfit(vector<int> &prices) {
if(prices.size() <= 1) return 0;
vector<int> dis;
dis.clear();
for(int i = 0; i < prices.size()-1; i++) {
int val = prices[i+1] - prices[i];
dis.push_back(val);
}
vector<int> cost;
cost.clear();
if(dis[0] <= 0) {
cost.push_back(0);
}
else {
cost.push_back(dis[0]);
}
for(int i = 1; i < dis.size(); i++) {
if(cost[i-1] + dis[i] >= 0) {
cost.push_back(cost[i-1] + dis[i]);
}
else {
cost.push_back(0);
}
}
int maxnow = 0;
for(int i = 0; i < cost.size(); i++) {
if(cost[i] < maxnow)
cost[i] = maxnow;
else {
maxnow = cost[i];
}
}
vector<int> cost_back;
cost_back.clear();
if(dis[dis.size()-1] <= 0) {
cost_back.push_back(0);
}
else {
cost_back.push_back(dis[dis.size()-1]);
}
for(int i = dis.size() - 2; i >= 0; i--) {
if(cost_back[dis.size()-2-i] + dis[i] >= 0) {
cost_back.push_back(cost_back[dis.size()-2-i] + dis[i]);
}
else {
cost_back.push_back(0);
}
}
maxnow = 0;
for(int i = 0; i < cost_back.size(); i++) {
if(cost_back[i] < maxnow)
cost_back[i] = maxnow;
else {
maxnow = cost_back[i];
}
}
int max = 0;
for(int i = 0; i < cost.size(); i++) {
if(cost.size() - 2 - i >= 0 && cost.size() - 2 - i < cost.size()) {
if(max < cost[i] + cost_back[cost.size()-2-i]) {
max = cost[i] + cost_back[cost.size()-2-i];
}
}
else {
if(max < cost[i])
max = cost[i];
}
}
return max;
}
};
|