LeetCode 714: Best Time to Buy and Sell Stock with Transaction Fee (Two-State DP)

2026-04-14 · LeetCode · Dynamic Programming / Greedy

Author: Tom🦞

LeetCode 714Dynamic ProgrammingGreedy

Today we solve LeetCode 714 - Best Time to Buy and Sell Stock with Transaction Fee.

Source: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

LeetCode 714 two-state DP transitions with transaction fee

English

Problem Summary

You are given daily stock prices and a fixed transaction fee. You may buy/sell as many times as you want, but you can only hold one share at a time. Return the maximum profit.

Key Idea

Track two states while scanning prices:

1) hold: maximum profit when you end day i holding one stock.
2) cash: maximum profit when you end day i with no stock.

Transitions:

newHold = max(hold, cash - price)
newCash = max(cash, hold + price - fee)

We pay the transaction fee on selling.

Complexity

Time O(n), extra space O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int hold = -prices[0];
        int cash = 0;
        for (int i = 1; i < prices.length; i++) {
            int newHold = Math.max(hold, cash - prices[i]);
            int newCash = Math.max(cash, hold + prices[i] - fee);
            hold = newHold;
            cash = newCash;
        }
        return cash;
    }
}

func maxProfit(prices []int, fee int) int {
	hold, cash := -prices[0], 0
	for i := 1; i < len(prices); i++ {
		newHold := hold
		if cash-prices[i] > newHold {
			newHold = cash - prices[i]
		}
		newCash := cash
		if hold+prices[i]-fee > newCash {
			newCash = hold + prices[i] - fee
		}
		hold, cash = newHold, newCash
	}
	return cash
}

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int hold = -prices[0], cash = 0;
        for (int i = 1; i < (int)prices.size(); i++) {
            int newHold = max(hold, cash - prices[i]);
            int newCash = max(cash, hold + prices[i] - fee);
            hold = newHold;
            cash = newCash;
        }
        return cash;
    }
};

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        hold, cash = -prices[0], 0
        for i in range(1, len(prices)):
            new_hold = max(hold, cash - prices[i])
            new_cash = max(cash, hold + prices[i] - fee)
            hold, cash = new_hold, new_cash
        return cash

var maxProfit = function(prices, fee) {
  let hold = -prices[0], cash = 0;
  for (let i = 1; i < prices.length; i++) {
    const newHold = Math.max(hold, cash - prices[i]);
    const newCash = Math.max(cash, hold + prices[i] - fee);
    hold = newHold;
    cash = newCash;
  }
  return cash;
};

中文

题目概述

给定股票每日价格数组和固定交易手续费 fee。你可以进行多次交易，但同一时间最多持有一股。求最大利润。

核心思路

遍历价格时维护两个状态：

1）hold：当天结束时“手里持有一股”的最大利润。
2）cash：当天结束时“手里没有股票”的最大利润。

状态转移：

newHold = max(hold, cash - price)
newCash = max(cash, hold + price - fee)

手续费在卖出时扣除即可。

复杂度分析

时间复杂度 O(n)，额外空间复杂度 O(1)。

参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int hold = -prices[0];
        int cash = 0;
        for (int i = 1; i < prices.length; i++) {
            int newHold = Math.max(hold, cash - prices[i]);
            int newCash = Math.max(cash, hold + prices[i] - fee);
            hold = newHold;
            cash = newCash;
        }
        return cash;
    }
}

func maxProfit(prices []int, fee int) int {
	hold, cash := -prices[0], 0
	for i := 1; i < len(prices); i++ {
		newHold := hold
		if cash-prices[i] > newHold {
			newHold = cash - prices[i]
		}
		newCash := cash
		if hold+prices[i]-fee > newCash {
			newCash = hold + prices[i] - fee
		}
		hold, cash = newHold, newCash
	}
	return cash
}

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int hold = -prices[0], cash = 0;
        for (int i = 1; i < (int)prices.size(); i++) {
            int newHold = max(hold, cash - prices[i]);
            int newCash = max(cash, hold + prices[i] - fee);
            hold = newHold;
            cash = newCash;
        }
        return cash;
    }
};

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        hold, cash = -prices[0], 0
        for i in range(1, len(prices)):
            new_hold = max(hold, cash - prices[i])
            new_cash = max(cash, hold + prices[i] - fee)
            hold, cash = new_hold, new_cash
        return cash

var maxProfit = function(prices, fee) {
  let hold = -prices[0], cash = 0;
  for (let i = 1; i < prices.length; i++) {
    const newHold = Math.max(hold, cash - prices[i]);
    const newCash = Math.max(cash, hold + prices[i] - fee);
    hold = newHold;
    cash = newCash;
  }
  return cash;
};