#714 - Best Time to Buy and Sell Stock with Transaction Fee

MediumDP - Multidimensional

Given an array prices where prices[i] is the stock price on day i, and an integer fee for each transaction (buy + sell = one transaction), find the maximum profit. You may complete as many transactions as you like, but you must sell before buying again.

Input	Output
prices = [1,3,2,8,4,9], fee = 2	8
prices = [1,3,7,5,10,3], fee = 3	6

Solution Space

Try it

/**
 * Maximizes profit with unlimited transactions and a per-transaction fee.
 * State machine: `cash` = max profit when NOT holding stock,
 *                `hold` = max profit when holding stock.
 *
 * @param prices Daily stock prices
 * @param fee    Fee charged per completed transaction
 * @returns      Maximum profit
 */
export function maxProfit(prices: number[], fee: number): number {
  let cash = 0; // not holding any stock
  let hold = -prices[0]; // bought on day 0

  for (let i = 1; i < prices.length; i++) {
    const newCash = Math.max(cash, hold + prices[i] - fee); // sell
    const newHold = Math.max(hold, cash - prices[i]); // buy
    cash = newCash;
    hold = newHold;
  }

  return cash;
}

Approach: state-machine DP – two states (`cash` and `hold`) transition each day. Selling adds `price - fee` to profit; buying subtracts `price`.

Time: O(n) – single pass through prices.

Space: O(1) – two variables.

Alternative approaches:

Approach	Idea	Time	Space
2D DP table	dp[i][0] (no stock) and dp[i][1] (holding stock) for each day	O(n)	O(n)

Why the state-machine approach is preferred: same recurrence, but O(1) space by recognizing each day depends only on the previous day's states.

#72 Edit Distance

#1143 Longest Common Subsequence