Best Time to Buy and Sell Stock with Transaction Fee (Java Recursion)

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example1 :

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Example 2:

Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6

Explanation (Program at the end of the page):

I have added inline comments, however you can skip those and read this instead as this is more descriptive.

The output is an integer which is the maximum profit. So return type is an integer.

The function takes 4 arguments :

1. i to iterate which acts as index of array
2. buy to check if you are trying to buy or sell. 1 means you have bought and the next operation you want to perform is sell. 0 means you have sold, and the next operation you want to perform is buy again.
3. prices array which is the input
4. fee is also an input which is the transaction cost while buying & selling

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8

We will begin with function call with array index 0 and 2nd argument i.e buy =0 which means our first operation is to buy.

profit(0,0,prices,fee)

Now there are two operations for every array element -

• Either we can buy/not buy
• We can sell/ not sell.

If buy=0, means we are trying to buy. Hence when we iterate we can either buy or not buy.

if(buy == 0) {
      return 
        Math.max(profit(i+1,1,prices,fee) - prices[i],
               profit(i+1,0,prices,fee));
 }

We can buy or not buy the share inside if. Correct ? Yes.
If we buy the share, we pass 1 to buy as 2nd parameter, as the next operation can only be sell, not buy. If we don’t buy, then the next operation will be buy, because we have not bought it, so we pass 0 to buy.

When we buy it i.e when we pass 1 to buy, we are also subtracting prices[i]; because amount = selling price of share -fee -cost price of share.

Hence in the above operation we subtract cost price of share which is prices[i].

else {
     return  
       Math.max(profit(i+1,0, prices,fee) + prices[i] - fee,
          profit(i+1,1,prices,fee));
}

else block means we are trying to sell (or we have already bought a share ) and the next operation can only be buy.

Now when we iterate over array elements, as we are trying to sell, so we can either sell or skip selling. If we sell, the next operation will be buy, so we pass 0 to buy as 2nd parameter; or if we do not sell, the next operation will be sell, so we will pass 1 to buy as 2nd parameter.

When we sell it i.e. when we pass 0 to buy as 2nd parameter, we will calculate the total amount.
Total amount = selling prices of share-fee-cost price of share.

In the above logic we subtract fee from the selling price. When do we subtract the cost price ? It is done inside if condition.

Recursive solution :

public class BuySellStockRecursion {
 

    public static int profit(int i,int buy,int [] prices,int fee) {
        
        if(i > prices.length-1){
            return 0;
        }

        /**
         * We Start from beginning
         *  Increase index because either you buy/sell or
         *  do not buy/sell
         *  index would increase
         *
         *  When you have not bought i.e buy == 0
         *  When you have bought and want to sell, then else
         *  When if true
         *  You can buy it or not buy
         *  If you buy call 1 as 2nd param so that it can only be sold
         *
         *  When else
         *  You can sell it or do not sell
         *  If you sell, call 0 as 2nd parameter so that it can only be bought
         */
        if(buy == 0) {
            return 
              Math.max(profit(i+1,1,prices,fee) - prices[i],
                    profit(i+1,0,prices,fee));
        }
        else {
            return  
           Math.max(profit(i+1,0, prices,fee) + prices[i] - fee,
                profit(i+1,1,prices,fee));
        }

    public static void main(String args[]) {
     System.out.println(profit(0,0,prices,fee));
    }
}

Conclusion
Please feel free to ask any question on comments. All the claps and follows are highly appreciated. Cheers!