Stock Buy and Sell

A family of problems on a price array $p_0,\dots ,p_{n-1}$, distinguished by how many transactions are allowed.

One transaction — $O(n)$

Buy once, sell once, later.

long long maxProfit1(const vector<int>& p) {
    long long best = 0; int minSoFar = p[0];
    for (int x : p) {
        best = max(best, (long long)x - minSoFar);
        minSoFar = min(minSoFar, x);
    }
    return best;
}

This is exactly Kadane on the difference array $p_i-p_{i-1}$ — the maximum subarray of daily changes.

Unlimited transactions — $O(n)$

Sum every upward move:

long long maxProfitInf(const vector<int>& p) {
    long long total = 0;
    for (int i = 1; i < (int)p.size(); i++)
        total += max(0, p[i] - p[i-1]);
    return total;
}

Any sequence of buys and sells telescopes into a sum of consecutive differences, so taking every positive one is optimal — a one-line exchange argument.

At most $k$ transactions — $O(nk)$

long long maxProfitK(const vector<int>& p, int k) {
    int n = p.size();
    if (k >= n / 2) return maxProfitInf(p);            // unlimited case
    vector<long long> buy(k + 1, LLONG_MIN / 2), sell(k + 1, 0);
    for (int x : p)
        for (int j = 1; j <= k; j++) {
            buy[j]  = max(buy[j],  sell[j-1] - x);     // hold after j-th buy
            sell[j] = max(sell[j], buy[j] + x);        // done after j-th sell
        }
    return sell[k];
}

The k >= n/2 shortcut matters: with enough transactions allowed, the constraint is vacuous, and it prevents an $O(nk)$ blowup when $k=10^9$.

The state-machine view

Every variant is a small DP over “how many transactions used” × “holding or not”:

       buy                sell
free ------> holding ------------> free (one more transaction used)

Adding a rule adds a state or an edge:

Rule	Change
Cooldown of 1 day after selling	add a cooldown state
Transaction fee $f$	subtract $f$ on each sell
At most $k$ transactions	index the states by $j$
Must hold $\ge d$ days	index by days held
Short selling allowed	add a symmetric short state

Once you draw the state machine, the code is mechanical. This is the clearest small example of DP as a state machine.

Huge $k$ — the Aliens trick

For $k$ up to $10^9$ with $n$ large, the $O(nk)$ DP is too slow. But the profit as a function of $k$ is concave (each extra transaction adds less), so Lagrangian relaxation applies:

1. Charge a penalty $\lambda$ per transaction.
2. Solve the unlimited version with that penalty in $O(n)$.
3. Binary search $\lambda$ until exactly $k$ transactions are used.
4. The answer is $\text{profit}(\lambda )+\lambda k$.

$O(n\log C)$ — independent of $k$. This is the canonical worked example for the Aliens trick, and worth studying for that reason alone.

The variant table

Variant	Method	Cost
One transaction	running minimum	$O(n)$
Unlimited	sum of positive differences	$O(n)$
At most 2	the $k=2$ DP, or forward/backward passes	$O(n)$
At most $k$	state DP	$O(nk)$
At most $k$, $k$ huge	Aliens trick	$O(n\log C)$
With cooldown	3-state DP	$O(n)$
With a fee	2-state DP	$O(n)$
Best time to buy and sell with short selling	4-state DP	$O(n)$

At most 2 transactions in $O(n)$

Two passes: left[i] = best profit using one transaction in $[0,i]$; right[i] = best in $[i,n)$. Then ${\max }_i(\mathrm{left}[i]+\mathrm{right}[i])$. The same prefix/suffix decomposition solves many “split the array into two independent parts” problems.

Why it is worth knowing

Three techniques appear in one small problem family:

1. Reduction to a known problem — one transaction is Kadane on differences.
2. State-machine DP — the general framework, extended by adding states.
3. Lagrangian relaxation — removing a “exactly $k$” constraint when the answer is concave in $k$.

See also: Kadane’s Algorithm · Aliens Trick · Introduction to DP