Valid for a single buy-sell cycle

The problem asks for the maximum possible profit from one purchase and one sale. A dynamic programming approach tracks two states for each day:

• cash_with_stock[i]: the largest amount of cash achievable on day i while holding the stock.
• cash_without_stock[i]: the largest amount of cash achievable on day i without holding the stock.

Formula derivation

When holding stock on day i, we either kept it from the previous day or bought it today. Buying costs today's price, and because only one transaction is allowed, the cash after buying is simply -prices[i].

cash_with_stock[i] = max(cash_with_stock[i-1], -prices[i])

When not holding on day i, we either were already without stock, or we sell the stock we held yesterday.

cash_without_stock[i] = max(cash_without_stock[i-1], cash_with_stock[i-1] + prices[i])

Initial values and traversal

Day 0 states: cash_with_stock[0] = -prices[0], cash_without_stock[0] = 0. Iterate from day 1 onward. The answer is cash_without_stock[last_day] because ending without stock always yields more cash.

// Single transaction allowed
int maxSingleProfit(vector<int>& prices) {
    int n = prices.size();
    if (n == 0) return 0;
    vector<vector<int>> state(n, vector<int>(2));
    state[0][0] = -prices[0];
    state[0][1] = 0;
    for (int i = 1; i < n; ++i) {
        state[i][0] = max(state[i-1][0], -prices[i]);
        state[i][1] = max(state[i-1][1], state[i-1][0] + prices[i]);
    }
    return state[n-1][1];
}

Valid for a unlimited number of transactions (but holding at most one share at a time)

The structure is almost identical. The only change is in the transition for cash_with_stock. When buying on day i, we can use the cash accumulated from previous sales, represented by cash_without_stock[i-1].

cash_with_stock[i] = max(cash_with_stock[i-1], cash_without_stock[i-1] - prices[i])

The sell logic stays the same:

cash_without_stock[i] = max(cash_without_stock[i-1], cash_with_stock[i-1] + prices[i])

Implementation

// Unlimited transactions
int maxMultiProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> state(n, vector<int>(2, 0));
    state[0][0] = -prices[0];
    for (int i = 1; i < n; ++i) {
        state[i][0] = max(state[i-1][0], state[i-1][1] - prices[i]);
        state[i][1] = max(state[i-1][1], state[i-1][0] + prices[i]);
    }
    return state[n-1][1];
}