Not as fast as dynamic solution but I didn't see it anywhere.

```
class Solution {
public:
int maxProfit(int K, vector<int>& prices) {
if(!K)
return 0;
vector<int> t;
for(int i=0, j=0; i<prices.size(); i++)
{
if(j == 0 && (i == prices.size()-1 || prices[i+1] > prices[i])
|| j == 1 && (i == prices.size()-1 || prices[i+1] < prices[i]))
{
t.push_back(prices[i]);
j = !j;
}
}
int n = t.size() - t.size() % 2;
int pre[n]; pre[0] = -1;
int suiv[n]; suiv[n-1] = -1;
set<pair<int, pair<int, int>>> s;
for(int i=1; i<n; i++)
{
s.insert({abs(t[i]-t[i-1]), {i-1, i}});
pre[i] = i-1;
suiv[i-1] = i;
}
int r = 0;
while(!s.empty())
{
auto p = s.begin()->second;
int j = p.first, k = p.second;
int i = pre[p.first], l = suiv[p.second];
if(s.size() <= 2*K-1)
r += s.begin()->first;
s.erase(s.begin());
if(i != -1)
{
s.erase(s.find({abs(t[j] - t[i]), {i, j}}));
suiv[i] = l;
}
if(l != -1)
{
s.erase(s.find({abs(t[l] - t[k]), {k, l}}));
pre[l] = i;
}
if(i != -1 && l != -1)
s.insert({abs(t[l] - t[i]), {i, l}});
}
return r;
}
};
```

We process in two steps:

- Firstly, we remove all the noise. For example, [1,2,3,4,3,2,4,5] becomes [1, 4, 2, 5].
- Secondly, a O(n^2) solution consists in erasing at each iteration the neighbors with the smallest absolute difference (in the example above, it's [4, 2]). To reduce the cost from O(n^2) to O(log n), we use a set, containing all absolute differences as well as indices corresponding to this differences. When we erase (i, j), we also have to erase (pre[i], i) and (j, next[j]), where pre[i] is the remaining indice preceding i and next[j] is the remaining indice following j, and we also have to add (pre[i], next[j]).