714. Best Time to Buy and Sell Stock with Transaction Fee
Problem
You are given an array prices where prices[i] is the price of a given stock on the iᵗʰ day, and an integer fee representing a transaction fee.
Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.
Note:
- You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
- The transaction fee is only charged once for each stock purchase and sale.
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
Example 1:
Input:
prices = [1,3,2,8,4,9], fee = 2
Output:8
Explanation: The maximum profit can be achieved by:
- Buying at
prices[0] = 1- Selling at
prices[3] = 8- Buying at
prices[4] = 4- Selling at
prices[5] = 9The total profit is
((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Example 2:
Input:
prices = [1,3,7,5,10,3], fee = 3
Output:6
Constraints:
1 <= prices.length <= 5 * 10⁴1 <= prices[i] < 5 * 10⁴0 <= fee < 5 * 10⁴
Test Cases
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:import pytest
from solution import Solution
@pytest.mark.parametrize('prices, fee, expected', [
([1,3,2,8,4,9], 2, 8),
([1,3,7,5,10,3], 3, 6),
])
@pytest.mark.parametrize('sol', [Solution()])
class Test:
def test_solution(self, sol, prices, fee, expected):
assert sol.maxProfit(prices, fee) == expected
Thoughts
系列问题:
- 121. Best Time to Buy and Sell Stock 最多交易 1 次
- 122. Best Time to Buy and Sell Stock II 交易任意多次
- 123. Best Time to Buy and Sell Stock III 最多交易 2 次
- 188. Best Time to Buy and Sell Stock IV 最多交易 k 次
- 309. Best Time to Buy and Sell Stock with Cooldown 交易任意多次,有冷静期
这次是在 122. Best Time to Buy and Sell Stock II(交易任意多次)的基础上,增加了每次交易的交易费。
在 122. Best Time to Buy and Sell Stock II 中已经定义了 动态规划的状态及其转移函数,那么直接在转移函数上,把交易费的影响加上去即可。更新后的转移函数为:
这里在卖出的时候扣除交易费。
同样是 O(n) 时间,O(1) 空间。
Code
class Solution:
def maxProfit(self, prices: list[int], fee: int) -> int:
max2 = lambda a, b: a if a >= b else b
hold = -prices[0]
empty = 0
for price in prices:
hold, empty = max2(hold, empty - price), max2(empty, hold + price - fee)
return empty
评论需要 JavaScript。