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] = 9

The 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

1
2
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
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

系列问题：

这次是在 122. Best Time to Buy and Sell Stock II（交易任意多次）的基础上，增加了每次交易的交易费。

在 122. Best Time to Buy and Sell Stock II 中已经定义了 动态规划的状态及其转移函数，那么直接在转移函数上，把交易费的影响加上去即可。更新后的转移函数为：

{holdi=max⁡{holdi−1,emptyi−1−prices[i]}emptyi=max⁡{emptyi−1,holdi−1+prices[i]−fee}\begin{cases} hold_i=\max\{hold_{i-1},empty_{i-1}-prices[i]\} \\ empty_i=\max\{empty_{i-1},hold_{i-1}+prices[i]-fee\} \end{cases}

这里在卖出的时候扣除交易费。

同样是 O(n) 时间，O(1) 空间。

Code

solution.py
1
2
3
4
5
6
7
8
9
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
medium
参考资料
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~