</>EmbeddedInterview

How do you calculate the maximum profit from buying and selling a stock?

MediumArrays & Strings (Coding Round)

Short answer: If you may make as many buy-sell trades as you like (holding at most one share at a time), add up every positive day-to-day increase: profit += max(0, price[i] - price[i-1]). If only one trade is allowed, track the minimum price so far and the best price - min (the maximum-difference problem).

#include <stddef.h>

/* unlimited transactions */
int max_profit_many(const int *price, size_t n)
{
    int profit = 0;
    for (size_t i = 1; i < n; i++)
        if (price[i] > price[i - 1])
            profit += price[i] - price[i - 1];
    return profit;
}
/* {1, 5, 3, 1, 2, 8} -> (5-1) + (2-1) + (8-2) = 4 + 1 + 6 = 11 */

/* one transaction (0 if prices only fall) */
int max_profit_one(const int *price, size_t n)
{
    if (n == 0) return 0;
    int min_price = price[0], best = 0;
    for (size_t i = 1; i < n; i++) {
        if (price[i] - min_price > best) best = price[i] - min_price;
        if (price[i] < min_price) min_price = price[i];
    }
    return best;
}
/* {1, 5, 3, 1, 2, 8} -> 7 (buy at 1, sell at 8) */

Why summing the rises is optimal: any profitable trade from day a to day b equals the sum of the daily changes between them. Taking only the positive changes is at least as good as any combination of trades, and it can be achieved by buying before each rise and selling after it.

Use the length you are given. A version that declares n = 5 but loops to a hard-coded 6 works by accident; pass n and loop i < n.

Dry run, unlimited: 1→5 (+4), 5→3 (skip), 3→1 (skip), 1→2 (+1), 2→8 (+6). Total 11.

Follow-ups: at most two transactions (track four states: first buy, first sell, second buy, second sell), a transaction fee (subtract the fee on each sell), or a cooldown day. These become small dynamic-programming state machines.