The idea of this thread was originally proposed by @yishiluo in
https://leetcode.com/discuss/26745/csolutionwithonklgntimeusingmaxheapandstack
General idea:
We use the term "valley" to denote a local minimum index of prices, and the term "peak" to denote a local maximum index of prices. Let (v1, p1) and (v2, p2) denote two successive valleypeak pairs of the prices, respectively. Consider the two cases:

Case 1: prices[v1] <= prices[v2] and prices[p1] <= prices[p2]. In this case, if we can conduct one transaction, we will use (v1, p2). If we can conduct two transactions, we will use (v1, p1) and (v2, p2). Equivalently, we can consider (v1, p2) as one transaction opportunity, and (v2, p1) as another transaction opportunity. The key idea is that these two original valleypeak pairs provide two transaction opportunities: (v1, p2) and (v2, p1).

Case 2: prices[v1] >= prices[v2] or prices[p1] >= prices[p2]. In this case, if we can conduct one transaction, we will use either (v1, p1) or (v2, p2). If we can conduct two transactions, we will use both (v1, p1) and (v2, p2). That is, these two valleypeak pairs provides two transaction opportunities: (v1, p1) and (v2, p2).
The algorithm consists of two steps:

Step 1: Find all transaction opportunities and record their profits. We use a stack
vps
to store the valleypeak pairs of the stock prices, wherein the valley value is sorted in ascending order. (The valley value at the top of the stack is the largest.) The profit of all transaction opportunities are recorded in the vectorprofits
. The time complexity of this step is O(n). 
Step 2: Find the k most profitable transaction opportunities. The maximum profit we can get is the summation of the k opportunity. The time complexity of this step is O(n), too.
Overall complexity:

Time: O(n)

Space: worsecase O(n)
C++ code (Accepted 8ms)
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
// Step 1: Find out all profit opportunities
vector<int> profits;
stack<pair<int, int>> vps; // valleypeak pairs
int v;
int p = 1;
for (;;) {
// find next valleypeak pair
for (v = p+1; (v+1 < prices.size()) && (prices[v] >= prices[v+1]); ++v);
for (p = v ; (p+1 < prices.size()) && (prices[p] <= prices[p+1]); ++p);
if (v == p) { // v==p means that both v and p reach the end of the array
break;
}
// Consider two transactions (v1, p1) (back of the stack) and (v2, p2) (the newfound).
// If prices[v1] >= prices[v2],
// it is meaningless to combine the two transactions.
// Save of profit of (v1, p1), and pop it out of the record.
while ((!vps.empty()) && (prices[v] <= prices[vps.top().first])) {
profits.push_back(prices[vps.top().second]  prices[vps.top().first]);
vps.pop();
}
// If prices[v1]<prices[v2] and prices[p1]<prices[p2],
// then it is meaningful to combine the two transactions
// update (v1, p1) to (v1, p2), and save the profit of (v2, p1)
while ((!vps.empty()) && (prices[p] >= prices[vps.top().second])) {
profits.push_back(prices[vps.top().second]  prices[v]);
v = vps.top().first;
vps.pop();
}
// save the newfound valleypeak pair
vps.emplace(v, p);
}
// save all remaining profits
while (!vps.empty()) {
profits.push_back(prices[vps.top().second]  prices[vps.top().first]);
vps.pop();
}
// Step 2: Calculate the k highest profits
int ret;
if (profits.size() <= k) {
ret = accumulate(profits.begin(), profits.end(), 0);
} else {
nth_element(profits.begin(), profits.end()  k, profits.end());
ret = accumulate(profits.end()  k, profits.end(), 0);
}
return ret;
}
};