Given an array of integers prices, Among them the first i Elements represent the i Day's share price ; Non-negative integer fee Represents the handling fee for trading shares .
You can close the deal indefinitely , But you have to pay a commission for every transaction . If you have bought a stock , You can't buy any more stock until you sell it .
Return the maximum profit .
Input : prices = [1, 3, 2, 8, 4, 9], fee = 2
Output : 8
explain : The maximum profit that can be achieved :
Buy... Here prices = 1
Sell... Here prices = 8
Buy... Here prices = 4
Sell... Here prices = 9
Total profit : ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Be careful :
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.
The general idea is similar to the second question in the stock question series ： The best time to buy and sell stocks ||
Because there is a service charge , So let's assume that when we buy stocks , You need to pay for it . So the transformation equation between States , Change is needed ：
As there is no limit to the number of shares to be traded , So there's no need to think about k and k-1 The problem of .
class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: if len(prices) == 0: return 0 n = len(prices) dp_i_0 = 0 dp_i_1 = -prices-fee for i in range(1,n): dp_i_0 = max(dp_i_0,dp_i_1+prices[i]) dp_i_1 = max(dp_i_1,dp_i_0-prices[i]-fee) return dp_i_0