Last Updated: 18 Nov, 2021
Best Time to Buy and Sell Stock with Transaction Fee
Moderate
Asked in companies
You are given an array 'prices' of size 'n', denoting the price of stocks on 'n' days.
Rahul can buy one stock at a time, and he must sell it before buying stock on another day.
The entire transaction of selling and buying the stock requires some transaction fee, given as 'fee'.
Find the maximum profit Rahul can achieve by trading on the stocks.
Example :
Input: 'prices' = [1, 2, 3] and 'fee' = 1
Output: 1
Explanation: We can generate the maximum profit of 1 by buying the stock on the first day for price = 1 and then selling it on the third day for price = 3.
The profit will be: 3 - 1 - 1(transaction fee) = 1
Input Format :
The first line contains integers 'n' and 'fee' denoting the number of days and the transaction fee.
The second line contains 'n' integers, denoting the price of stocks on each day.
Output format :
Print the maximum profit Rahul can achieve by trading on the stocks.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Approaches
Let dp[i][status] be the maximum profit in the first i days when:
'status' = 0 means we are not having any stock on the i-th day.
'status' = 1 means we are having a stock on the i-th day.
Every day, we have 2 choices:
If we have a stock, either sell it or not.
If we don't have stock, either buy it or not.
Depending on these, we will write our transitions.
Our final answer will be dp[n][0] because this the the maximum profit after 'n' days and not having any stock with us.
Algorithm:
- Let 'dp' be a matrix of dimensions ('n' + 1) * 2.
- Base case: dp[0][0] = 0 and dp[0][1] = -infinity, because we cannot already have a stock.
- For 'i' in range from 1 to 'n' (inclusive):
- dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1] - fee)
- dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1])
- Return dp[n][0].
Approach: Let us main two states for the solution:
p1 = Profit when we have no chocolate.
p2 = Profit when we have one chocolate.
We will iterate through the array 'prices' and update the above variables greedily. Our answer will be p1, i.e., profit after selling the chocolate.
In the iteration, let p be the price of chocolate on the current day.
We can update our states by selling the current chocolate from p2 i.e we will do p1 = max(p1, p2 + p)
Also, we can do it by buying the chocolate from p1 i.e p2 = max(p2, p1 - p - fee)
Algorithm :
- Initialize the variables 'p1' and ‘p2’ with -infinity.
- For 'p' in 'prices':
- Assign ‘p1’ with a maximum of ‘p1’ and ‘p2’ + ‘p’.
- Make ‘p2’ as a maximum of ‘p2’ and ‘p1’ - ‘p’ - ‘fee’.
- Finally return the max profit 'p1'.