You are given an integer array of prices where prices[i] is the price of a given stock on the ith day and an integer k.
Find the maximum profit you can achieve. You may complete at most k transactions, where each transaction incurs a transaction fee as a percentage of the transaction amount. You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Write a function to calculate the maximum profit considering the transaction fee.
Parameters:
K: An integer representing the maximum number of transactions allowed.
prices: An array of integers representing the prices of the stock on each day.
fee: A number representing the transaction fee as a percentage of the transaction amount.
Here’s a function to calculate the maximum profit considering the transaction fee:
def max_profit_with_fee(k, prices, fee):
"""
This function calculates the maximum profit achievable with k transactions
and a transaction fee.
Args:
k: Maximum allowed transactions.
prices: Array of stock prices.
fee: Transaction fee as a percentage.
Returns:
Maximum achievable profit.
"""
# Handle edge cases
if not prices or k == 0:
return 0
n = len(prices)
# Initialize arrays to store maximum profit at each day
# under two conditions: holding stock or not holding
# (cash) considering k transactions
dp = [[0 for _ in range(2)] for _ in range(k + 1)]
# No transaction on day 0 (both cash and holding states)
dp[0][0] = dp[0][1] = 0
# Iterate through prices for each transaction (0 to k)
for i in range(1, n):
for j in range(k, 0, -1):
# Cash on day i:
# - Either stay in cash (previous cash)
# - Or sell stock from previous holding state (considering fee)
dp[j][0] = max(dp[j][0], dp[j][1] + prices[i] - fee * prices[i] / 100)
# Holding stock on day i:
# - Either stay holding (previous holding)
# - Or buy stock from previous cash state
dp[j][1] = max(dp[j][1], dp[j - 1][0] - prices[i])
# Return the maximum profit achievable with k transactions (cash state)
return dp[k][0]
Explanation:
k
, prices
, and fee
as input.dp
of size (k+1) x 2
. This array will store the maximum profit achievable with k
transactions at each day (i
) under two conditions: holding a stock (dp[j][1]
) or having cash (dp[j][0]
).dp[0][0]
and dp[0][1]
to 0 as there are no transactions on day 0.k
down to 1).i
).dp[j][0]
), it considers two options:
dp[j][1]
), it considers two options:
dp[j][0]
and dp[j][1]
with the maximum of the two options for each state.dp[k][0]
, which represents the maximum achievable profit with k
transactions (cash state) after considering all days and transaction options.This approach uses dynamic programming to efficiently calculate the maximum profit considering the transaction fee and the constraint on the number of transactions.