188. Best Time to Buy and Sell Stock IV

There are two kinds of algorithms to solve this problem. First one is to use MAX_HEAP and STACK.

The basic idea is to find all adjacent bottom/top paris and compute the profits from the pairs (top - bottom). we get k largest profits as the result. There are three cases:

Case 1:
When there are two adjacent pairs of bottom/top, i.e. [b1, t1] and [b2, t2] satisfying b1 > b2 (no matter of top). Obviously, there need to be two transactions to achieve the max profit. And if only one transaction allowed, the answer will be in either [b1, t1] or [b2, t2] (no merge is required because b1 > b2 then t2-b2 > t2 - b1).

Case 2:
When there are two adjacent pairs of bottom/top, i.e. [b1, t1] and [b2, t2] satisfying b1 <= b2 and t1 > t2. In this case, there need to be two transactions to achieve the max profit. HOWEVER, in case of "Case 3" following, where pairs will be merged backward, we need to push the pairs in stack and compute profits later.

Case 3:
When there are two adjacent pairs of bottom/top, i.e. [b1, t1] and [b2, t2] satisfying b1 <= b2 and t1 <= t2, we can either make one transaction by [b1, t2] or two transactions by [b1, t1] and [b2, t2]. Note, it's impossible for t1 <= b2 as [b1, t1] and [b2, t2] are adjacent each other and t1 is a top which means t1 > b2.  The trick here is to treat [t1, b2] as first transaction and [b1, t2] as second transaction. By doing so, profit [t1, b2] will be saved in max heap and the two bottom/top pair [b1, t1] and [b2, t2] will be merged to [b1, t2]. This procedure will be repeated until there is no pairs in stack. At the end the profit of [b1, t2] will be stocked in max heap.

Some examples:
[3, 9, 4, 8, 5, 9]
Round1:
Stack = [(3, 9)], Profit = []
Round 2 (Case 2):
Stack = [(3, 9), (4, 8)], Profit = []
Round 3 (Case 3):
loop 1: Stack = [(3, 9)], Profit = [3], merged pair (4, 9)
loop 2: Stack = [], Profit = [5, 3], merged pair (3, 9)
Stack = [(3, 9)],  Profit = [5, 3]
In the end, Profit = [6, 5, 3]

1:  class Solution {  
2:  public:  
3:    int maxProfit(int k, vector<int>& prices) {  
4:      int n = prices.size();  
5:      if (n == 0) return 0;  
6:      stack<pair<int, int>> stk;  
7:      priority_queue<int> profits;  
8:      int bottom = 0, top = 0;  
9:      int sum = 0;  
10:      while (top < n) {  
11:        // search for next bottom and top  
12:        for (bottom = top; bottom < n-1 && prices[bottom] > prices[bottom+1]; bottom++);  
13:        for (top = bottom+1; top < n && prices[top-1] <= prices[top]; top++);  
14:        // CASE 1: current bottom is lower than the bottom of last adjacent interval  
15:        while (!stk.empty() && prices[bottom] < prices[stk.top().first]) {  
16:          profits.push(prices[stk.top().second-1] - prices[stk.top().first]);  
17:          stk.pop();  
18:        }  
19:        while (!stk.empty() && prices[bottom] >= prices[stk.top().first] && prices[top-1] >= prices[stk.top().second-1]) {  
20:          profits.push(prices[stk.top().second-1] - prices[bottom]);  
21:          bottom = stk.top().first;  
22:          stk.pop();  
23:        }  
24:        stk.push(pair<int, int>(bottom, top));  
25:      }  
26:      while (!stk.empty()) {  
27:        profits.push(prices[stk.top().second-1] - prices[stk.top().first]);  
28:        stk.pop();  
29:      }  
30:      for (int i = 0; i < k && !profits.empty(); i++) {  
31:        sum += profits.top();  
32:        profits.pop();  
33:      }  
34:      return sum;  
35:    }  
36:  };