Problem

I just came across this problem on Leet: 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).

Naive solution

dp[i][j] := Maximum net profit having i days passed and j trades occured.

Note that although a transaction includes buying and selling, we’ll count buying and selling as individual trades. This way we can discern whether the last trade was buying or selling by the parity of j.

The transition is simple:

dp[i][j] = max( dp[i - 1][j], dp[i - 1][j - 1] + (j is even ? -1 : +1) * prices[i] )

The time complexity is obviously O(NK).

Observations

1. There are NK states, so if we are going to stick with DP, it’s likely we need to get rid of K.
2. Let f(x) := Maximum net profit having x transactions.
   An interesting property emerges: f(x + 1) - f(x) <= f(x) - f(x - 1) ∀ x
   That is, f plotted on a 2D plane is a concave downward parabola.

Let’s consider a similar problem

Instead of having the constraint “at most K transactions can occur”, let’s assign each transaction with some fixed cost.
This problem can be solved easily in O(N), along with the minimum number of transactions required for the maximum profit:
Also, it’s intuitive that the larger the cost is, the less transactions should occur in the optimal solution, and vice versa.
Let’s say there exists some C, such that the optimal solution with unbounded transactions but has an extra cost of C for each transaction makes exactly K transactions.
How do we know if there exists such C?
Remember the second observation in the orignal problem?
f(x + 1) - f(x) <= f(x) - f(x - 1) ∀ x
So basically what we have now is:
f(K) - f(K - 1) >= C >= f(K + 1) - f(K) >= f(K + 2) - f(K + 1) >= …
So it’s obvious such C always exists, and we can find it with binsearch.
It’s also clear that the optimal solution in this context + C * K is the optimal solution in the original problem.

Solution

class Solution { // O(N lg P)
 public:
  int maxProfit(int k, vector<int>& prices) {
    if (prices.empty()) return 0;

    const int n = prices.size();
    const int maxp = *max_element(prices.begin(), prices.end()) -
                     *min_element(prices.begin(), prices.end());

    auto dp = [&](int c) {
      vector<pair<int, int>> d(2);
      d[1] = make_pair(-prices[0], -0);
      for (int i = 1; i < n; ++i) {
        pair<int, int> nd0 = d[1];
        nd0.first += prices[i] - c;
        nd0.second -= 1;
        pair<int, int> nd1 = d[0];
        nd1.first -= prices[i];
        d[0] = max(d[0], nd0);
        d[1] = max(d[1], nd1);
      }
      d[0].second *= -1;
      return d[0];
    };

    int lb = -1;
    int ub = maxp;
    while (ub - lb > 1) {
      int mb = lb + ub >> 1;
      (dp(mb).second <= k ? ub : lb) = mb;
    }

    return dp(ub).first + ub * k;
  }
};

Reference

This slide on IOI2016-Alien gives an explanation in depth on the problem “Alien” that made this trick popular.