Best Time to Buy and Sell Stock with Transaction Fee
DP on Stocks DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Maximize profit from stock trading with transaction fee (Dynamic Programming Approaches), Dynamic Programming, Memoization, Tabulation, Space Optimization, Recursion, Overlapping Subproblems, Optimal Substructure, Arrays, Time Complexity, Space Complexity, Base Cases, Optimization, Stack, Subsequences, dynamic programming, memoization, problem specific, tabulation, space optimization, recursion, DP State Management, Stock Problems.
Problem Statement You are given an array prices of length n, where prices[i] is the price of a given stock on the i th day. You are also given an integer fee, which is a transaction fee. You can buy and sell the stock any number of times. However, you must buy a stock before you can sell it. Also, you cannot buy a stock again until you have sold the previously bought stock. After every transaction (buy and sell), there is a transaction fee associated with it. Your task is to find the maximum profit you can achieve. Input Format The first line contains an integer n, the number of days. The second line contains n space separated integers representing the prices array. The third line contains an integer fee, the transaction fee. Output Format Print a single integer representing the maximum profit. Constraints Constraints are not provided in the original content. Sample Test Cases Input: Output: Explanation: Buy on day 0 (price = 1), sell on day 1 (price = 3). Profit = (3 1) 2 = 0. Buy on day 3 (price = 2), sell on day 5 (price = 8). Profit = (8 2) 2 = 4. Buy on day 4 (price = 4), sell on day 5 (price = 9). Profit = (9 4) 2 = 3. Total profit = 0 + 4 + 3 = 7. Wait, the example output is 8. Let's re evaluate. Buy on day 0 (price = 1) Sell on day 3 (price = 8) Profit = (8 1) 2 = 5 Buy on day 4 (price = 4) Sell on day 5 (price = 9) Profit = (9 4) 2 = 3 Total profit = 5 + 3 = 8. This strategy gives the maximum profit.