🚀 Stock Trading with Fee: Optimal DP Solution in Python | LeetCode 75 #Python #DP #Stocks #LeetCode

Problem Overview:

In this problem, you are given an array prices where prices[i] is the price of a given stock on the i-th day, and an integer fee representing a transaction fee. You can complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the restriction that you cannot engage in multiple transactions simultaneously. For each transaction, you incur a transaction fee.
The goal is to find the maximum profit you can achieve after paying all transaction fees.

Key Points:

You can only hold at most one share of the stock at a time.

Each time you sell, you pay the fee.

The solution must be efficient given that the length of prices can be up to 5×10⁴.

Approach: Dynamic Programming (DP) with Two Variables
We use a DP approach that tracks two states for each day:

Cash: The maximum profit you can have if you do not hold any stock.

Hold: The maximum profit you can have if you are holding one stock.

Transitions:

When you sell a stock on day i, the profit becomes hold + prices[i] - fee.

When you buy a stock on day i, the profit becomes cash - prices[i].

We initialize:

cash = 0 (starting with no stock and no profit)

hold = -prices[0] (if you buy on the first day, you lose prices[0] dollars)

Then for each subsequent day, we update:

prev_cash = cash
cash = max(cash, hold + price - fee) # Sell stock today, or do nothing
hold = max(hold, prev_cash - price) # Buy stock today, or do nothing

Finally, the answer is the value of cash after processing all days, which represents the maximum profit with no stock held.

Python Code Implementation:

class Solution:
def maxProfit(self, prices, fee):
if not prices:
return 0

cash = 0
hold = -prices[0]

for price in prices[1:]:
prev_cash = cash
cash = max(cash, hold + price - fee)
hold = max(hold, prev_cash - price)

return cash

# Example Usage:

sol = Solution()

Complexity Analysis:

Time Complexity: O(n) – We iterate through the prices array once.

Space Complexity: O(1) – Only a few variables are used to track the state.

#LeetCode75, #Python, #DynamicProgramming, #DP, #Stocks, #Algorithm, #Coding, #ProblemSolving, #Trading, #CodingInterview