My idea:

**1)** Find all valley and peek pairs (buy at valley point and sell at peek point) . ( in O(n) time)

input: 6 1 3 2 4 7 6 10 15

output of this step: (1, 3), (2,7), (6, 15)

**2)** Find the split point that maximize profit, since we can complete at most two transactions. (in O(m^2), m is the number of pairs generated in step 1)

total_profit = 0

for i =0 to m-1:

`first transaction complete before pair[i] ( include pair[i]) compute max profit of the first transaction in O(i) second transaction complete after pair[i] (exclude pair[i]) compute max profit of the second transaction in O(m-i) total_profit = max( total_profit, first + second)`

my accepted code:

```
int maxProfit(vector<int> &prices) {
// step 1, find pairs
vector<int> lows; // local low points
vector<int> highs; // local peek points
int n = prices.size();
int i = 0;
while(i < n) {
while(i+1<n && prices[i+1] <= prices[i]) ++i;
lows.push_back(prices[i]);
while(i+1<n && prices[i+1] >= prices[i]) ++i;
highs.push_back(prices[i]);
++i;
}
// step 2: split
int total_profit = 0;
n = lows.size();
for (i = 0; i < n; ++i) {
int j = 0;
int low = INT_MAX;
int high = 0;
int first = 0; // max profit of the first transaction
int second = 0; // max profit of the second transaction
while (j <= i) {
low = min(low, lows[j]);
high = highs[j];
first = max(first, high-low);
++j;
}
low = INT_MAX;
high = 0;
j = i+1;
while (j < n) {
low = min(low, lows[j]);
high = highs[j];
second = max(second, high - low);
++j;
}
total_profit = max(total_profit, first + second);
}
return total_profit;
}
```

**I think there are better solutions, but I haven't got it - -
Anybody has one to share ?**