Best Time to Buy and Sell Stock with Transaction Fee

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
46 upvotes
Asked in companies
IBMAmazonFacebook

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
3 1
1 2 3


Sample Output 1 :
1


Explanation Of Sample Input 1 :
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


Sample Input 2 :
4 2
1 3 5 6


Sample Output 2 :
3


Expected time complexity :
The expected time complexity is O(n).


Constraints :
1 <= 'n' <= 10 ^ 4
0 <= 'prices[i]' <= 10 ^ 5
0 <= 'fee'<= 10 ^ 5
Hint

Try solving using Dynamic Programming.

Approaches (2)
Dynamic Programming

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].
Time Complexity

O(n), where 'n' is the size of the array 'prices'

As we are iterating over the array running the loop 'n' times, the time complexity will be O(n).

Space Complexity

O(n), where 'n' is the size of the array 'prices'

As we are creating a matrix of dimensions ('n' + 1) * 2, the space complexity will be O(n).

Code Solution
(100% EXP penalty)
Best Time to Buy and Sell Stock with Transaction Fee
Full screen
Console