Best Time To Buy Sell Stock IV

题目

Best Time to Buy and Sell Stock IV
Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

解题报告

思路

• 获取收益肯定应该在地点买入，高点卖出，假定 vally 表示低价格的索引，peak 表示高价格的索引，因此 (v1, p1) 和 (v2, p2) 表示两个连续的 valley-peak 的价格。考虑如下两个 case
  * prices[v1] <= prices[v2] && prices[p1] <= prices[p2]，在该条件下，如果只能交易一次，那就是(v1, p2)。 如果是两个交易，那就是(v1, p1) 和 (v2, p2)。为了省事，将(v1, p2)看做为第一个交易，(v2, p1) 看做第二个交易.
• prices[v1] >= prices[v2] || prices[p1] >= prices[p2]，在该条件下，如果只能交易一次，要么就用(v1,p1)，要么就用 (v2,p2)。如果是两次交易，就全部使用。

步骤

• 找到全部的交易，并且记录每一笔的收益，使用 stack 记录每一对 vally-peak 。并且保证 vally 是按照升序排列。所有的收益都放在 vector 数组中，时间复杂度为 O(n).
• 找到前 k 个交易收益，时间复杂度为 O(n)

代码

class Solution{
public:
    int maxProfit(int k, vector<int>& prices){
        const int m = prices.size();
        vector<int> profits;
        stack<pair<int,int>> vps; // vally-peak pairs
        int v = 0, p = -1; // padding p , so not using p-1
        while (true) {
            // find next vally and peak
            for (v = p+1; v+1 < m && (prices[v] >= prices[v+1]); v++);
            for (p = v;   p+1 < m && (prices[p] >= prices[p-1]); p++);
            if (v == p) break; // to the end of prices

            // v < p

            // (v1,p1) (v2,p2)
            // if (prices[v1] >= prices[v2]) no need to combine two transactions
            // after å top is (v1,p2), push p2-v1 into profit --> step ∑
            while (!vps.empty() && (prices[v] <= prics[vps.top().first])) {
                profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
                vps.pop();
            }

            // (v1, p1) (v2,p2)
            // if (prices[v1] < prices[v2] && prices[p1] < prices[p2]) we need to combine two transactions
            // update (v1,p1) --> (v1, p2)
            // p2-v2 + p1-v1 == p2-v1 + p1-v2
            // after step ∑ top is (v1, p2)
            while (!vps.empty() && (prices[p] >= prices[vps.top().second])) {
                // save profit (v2, p1)
                profits.push_back(prices[vps.top().second] - prices[v]);
                // v1 --> v
                v = vps.top()first;
                vps.pop();
                // v is v1
                // p is p2
                // step å
            }
            // if step å  (v1, p2) is top of vps
            vps.push(make_pair(v, p));
        }
    }

    // calculate all the profits
    while (!vps.empty()) {
        profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
        vps.pop();
    }

    // calculate k highest profitœ
    int ans = 0;
    const int n = profits.size();
    if (n < = k) {
        accumulate(profits.begin(), profits.end(), 0);
    } else {
        nth_element(profits.begin(), profits.end() - k, profits.end());
        accumulate(profits.end() - k,profit.end(), 0);
    }
    return ans;
};