Best Time to Buy and Sell Stock with Transaction Fee

Moderate

0/80

Average time to solve is 20m

Contributed by

42 upvotes

Asked in companies

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 :

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 :

Expected time complexity :

The expected time complexity is O(n).

Constraints :

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

Console