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: };
