Best time to buy and sell stock with transaction fees

Upon observation, we find that every day, there will be two choices, either to do nothing and move to the next day or to buy/sell (based on the last transaction and the number of transactions left) and find out the profit. Therefore we need to generate all the choices in order to compare the profit. As all possible choices needs to be generated, we will use recursion.

Steps to form the recursive solution:

Express the problem in terms of indexes: We need to think in the terms of the number of days, therefore one variable will be the array index( say ind). Next, we need to consider the condition that a stock can't be bought again, that is we need to first sell a stock, and then we can buy that again. Therefore a second variable ‘buy’ is needed, which tells, on a particular day whether we can buy or sell the stock. Next, there is a fee applied on every complete transaction. So in order to keep track of this, one more variable will be needed (say 'fee').

f(ind, buy, fee) will give the maximum profit that can be generated from day 'ind' to day (n-1), where 'buy' tells that whether we need to buy or sell the stock at day 'ind' and 'fee' tells the fee incurred at every complete transaction.

Try out all possible choices at a given index: Every day, there will be two choices, either to buy/sell the stock(based on the buy variable’s value) or to do nothing and move on to the next day. As we need to generate all the choices, use the pick/non-pick technique to the same.

Case 1: When buy == 0, the stock can be bought. If we can buy the stock on a particular day, there will be two options:

Option 1: To do no transaction and move to the next day. In this case, the net profit earned will be 0 from the current transaction, and to calculate the maximum profit starting from the next day, we will recursively call f(ind+1, 0, fee). As we have not bought the stock, the ‘buy’ variable value will still remain 0, indicating that stock can be bought on next day.

Option 2: The other option is to buy the stock on the current day. In this case, the net profit earned from the current transaction will be -Arr[i]. As we are buying the stock, we are giving money out of our pocket, therefore the profit we earn is negative. To calculate the maximum profit starting from the next day, recursively call f(ind+1,1, fee). As the stock has been bought, the ‘buy’ variable value will change to 1, indicating that we can’t buy and only sell the stock the next day.

Case 2: When buy == 1, we can sell the stock. If we can sell the stock on a particular day, we will have two options:

Option 1: To do no transaction and move to the next day. In this case, the net profit earned will be 0 from the current transaction, and to calculate the maximum profit starting from the next day, we will recursively call f(ind+1,1, fee). As we have not bought the stock, the ‘buy’ variable value will still remain at 1, indicating that we can’t buy and only sell the stock the next day.

Option 2: The other option is to sell the stock on the current day. In this case, the net profit earned from the current transaction will be +Arr[i]. As we are selling the stock, we are putting the money into our pocket, therefore the profit we earn is positive. Next, as we have bought and sold the stock, one complete transaction has been made. Hence the transaction fees will be incurred. So subtract that from the profit earned. To calculate the maximum profit starting from the next day, we will recursively call f(ind+1, 0, fee). As we have sold the stock, the ‘buy’ variable value will change to 0, indicating that we can buy the stock the next day.

Note: Buying and selling a stock together counts as one complete transaction. Therefore the fee will be deducted once after selling every stock.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(ind, buy, fee){
    //Base case
    if(buy == 0){
        op1 = 0 + f(ind + 1, 0, fee)
        op2 = -arr[ind] + f(ind + 1, 1, fee)
    }
    if(buy == 1){
        op1 = 0 + f(ind + 1, 1, fee)
        op2 = arr[ind] - fee + f(ind + 1, 0, fee)
    }
           
}

Take the maximum of all choices: As we are looking to maximize the profit earned, return the maximum value in both cases.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(ind, buy, fee){
    //Base case
    if(buy == 0){
        op1 = 0 + f(ind + 1, 0, fee)
        op2 = -arr[ind] + f(ind + 1, 1, fee)
    }
    if(buy == 1){
        op1 = 0 + f(ind + 1, 1, fee)
        op2 = arr[ind]  - fee + f(ind + 1, 0, fee)
    }
    return max(op1, op2)    
}

Base cases: There be will only one base case, when ind==n, it means we have finished trading on all days, and no more profit can be made, therefore simply return 0.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    //Function to find the maximum profit earned using recursion
    int func(int ind, int buy, int fee, int n, vector<int> &arr) {
        // Base case 
        if (ind == n) {
            return 0;
        }

        int profit;
        
        // We can buy the stock
        if (buy == 0) { 
            profit = max(0 + func(ind + 1, 0, fee, n, arr), (-1)*arr[ind] + func(ind + 1, 1, fee, n, arr));
        }
        
        //We can sell the stock
        if (buy == 1) { 
            profit = max(0 + func(ind + 1, 1, fee, n, arr), arr[ind]-fee + func(ind + 1, 0, fee, n, arr));
        }

        // Return the calculated profit
        return profit;
    }
public:
    //Function to calculate the maximum profit earned 
    int stockBuySell(vector<int> &arr, int n, int fee) {
        if (n == 0) 
            return 0;

        int ans = func(0, 0, fee, n, arr);
        
        //Return the maximum profit
        return ans;
    }
};
int main() {
    int n = 5;
    vector<int> arr = {1, 3, 4, 0, 2};
    int fee = 1;
    
    //Create an instance of Solution class
    Solution sol;

    // Call the stockBuySell function and print the result
    cout << "The maximum profit that can be generated is " << sol.stockBuySell(arr, n, fee);

    return 0;
}
import java.util.*;

class Solution {
    // Function to find the maximum profit earned using recursion
    private int func(int ind, int buy, int fee, int n, int[] arr) {
        // Base case 
        if (ind == n) {
            return 0;
        }

        int profit = 0;
        
        // We can buy the stock
        if (buy == 0) { 
            profit = Math.max(0 + func(ind + 1, 0, fee, n, arr), (-1)*arr[ind] + func(ind + 1, 1, fee, n, arr));
        }
        
        // We can sell the stock
        if (buy == 1) { 
            profit = Math.max(0 + func(ind + 1, 1, fee, n, arr), arr[ind]-fee + func(ind + 1, 0, fee, n, arr));
        }

        // Return the calculated profit
        return profit;
    }

    // Function to calculate the maximum profit earned 
    public int stockBuySell(int[]arr, int n, int fee) {
        if (n == 0) 
            return 0;

        int ans = func(0, 0, fee, n, arr);
        
        // Return the maximum profit
        return ans;
    }

    public static void main(String[] args) {
        int n = 8;
        int[] arr = {3, 3, 5, 0, 0, 3, 1, 4};
        int fee = 1;
        
        // Create an instance of Solution class
        Solution sol = new Solution();

        // Call the stockBuySell function and print the result
        System.out.println("The maximum profit that can be generated is " + sol.stockBuySell(arr, n, fee));
    }
}
class Solution:
    # Function to find the maximum profit earned using recursion
    def func(self, ind, buy, fee, n, arr):
        # Base case 
        if(ind == n):
            return 0

        profit = 0
        
        # We can buy the stock
        if buy == 0:
            profit = max(0 + self.func(ind + 1, 0, fee, n, arr), (-1)*arr[ind] + self.func(ind + 1, 1, fee, n, arr))
        
        # We can sell the stock
        if buy == 1:
            profit = max(0 + self.func(ind + 1, 1, fee, n, arr), arr[ind]-fee + self.func(ind + 1, 0, fee, n, arr))

        # Return the calculated profit
        return profit

    # Function to calculate the maximum profit earned 
    def stockBuySell(self, arr, n, fee):
        if n == 0:
            return 0

        ans = self.func(0, 0, fee, n, arr)
        
        # Return the maximum profit
        return ans

if __name__ == "__main__":
    n = 8
    arr = [3, 3, 5, 0, 0, 3, 1, 4]
    fee = 1
    
    # Create an instance of Solution class
    sol = Solution()

    # Call the stockBuySell function and print the result
    print("The maximum profit that can be generated is", sol.stockBuySell(arr, n, fee))
class Solution {
    // Function to find the maximum profit earned using recursion
    func(ind, buy, fee, n, arr) {
        // Base case 
        if (ind === n) {
            return 0;
        }

        let profit = 0;
        
        // We can buy the stock
        if (buy === 0) { 
            profit = Math.max(0 + this.func(ind + 1, 0, fee, n, arr), (-1)*arr[ind] + this.func(ind + 1, 1, fee, n, arr));
        }
        
        // We can sell the stock
        if (buy === 1) { 
            profit = Math.max(0 + this.func(ind + 1, 1, fee, n, arr), arr[ind]-fee + this.func(ind + 1, 0, fee, n, arr));
        }

        // Return the calculated profit
        return profit;
    }

    // Function to calculate the maximum profit earned 
    stockBuySell(arr, n, fee) {
        if (n === 0) 
            return 0;

        let ans = this.func(0, 0, fee, n, arr);
        
        // Return the maximum profit
        return ans;
    }
}

function main() {
    const n = 8;
    const arr = [3, 3, 5, 0, 0, 3, 1, 4];
    const fee = 1;
    
    // Create an instance of Solution class
    const sol = new Solution();

    // Call the stockBuySell function and print the result
    console.log("The maximum profit that can be generated is", sol.stockBuySell(arr, n, fee));
}

main();

Time Complexity: O(2^(N)), where N is the number of row. As, for each index, ther are two possible options.

Space Complexity:O(N), at maximum the depth of the recursive stack can go upto N.

If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.

In order to convert a recursive solution to memoization the following steps will be taken:

Declare a dp array of size [n][2]: As there are two changing parameters in the recursive solution, 'ind' and 'buy' (third parameter of the recusive solution is 'fee' which remains fixed throughout). The maximum value 'ind' can attain is (n), where n is the size of array and for 'buy' only two values possible 0, 1.

The dp array stores the calculations of subproblems. Initialize dp array with -1, to indicate that no subproblem has been solved yet.

While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.

Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    //Function to find the maximum profit earned using memoization
    int func(int ind, int buy, int fee, int n, vector<int> &arr, vector<vector<int>>& dp) {
        // Base case 
        if (ind == n) {
            return 0;
        }
        /* If the result for this state has 
        already been calculated, return it*/
        if (dp[ind][buy] != -1) {
            return dp[ind][buy];
        }
        int profit = 0;
        
        // We can buy the stock
        if (buy == 0) { 
            profit = max(0 + func(ind + 1, 0, fee, n, arr, dp), (-1)*arr[ind] + func(ind + 1, 1, fee, n, arr, dp));
        }
        
        //We can sell the stock
        if (buy == 1) { 
            profit = max(0 + func(ind + 1, 1, fee, n, arr, dp), arr[ind]-fee + func(ind + 1, 0, fee, n, arr, dp));
        }

        /* Store the value in dp array and
        return the calculated profit */
        return dp[ind][buy] = profit;
    }
public:
    //Function to calculate the maximum profit earned 
    int stockBuySell(vector<int> &arr, int n, int fee) {
        if (n == 0) 
            return 0;
            
        // Initialize a DP table to memoize results
        vector<vector<int>> dp(n, vector<int>(2, -1));

        int ans = func(0, 0, fee, n, arr, dp);
        
        //Return the maximum profit
        return ans;
    }
};
int main() {
    int n = 8;
    vector<int> arr = {3, 3, 5, 0, 0, 3, 1, 4};
    int fee = 1;
    
    //Create an instance of Solution class
    Solution sol;

    // Call the stockBuySell function and print the result
    cout << "The maximum profit that can be generated is " << sol.stockBuySell(arr, n, fee);

    return 0;
}


import java.util.*;

class Solution {
    // Function to find the maximum profit earned using memoization
    private int func(int ind, int buy, int fee, int n, int[] arr, int[][] dp) {
        // Base case 
        if (ind == n) {
            return 0;
        }
        /* If the result for this state has 
        already been calculated, return it*/
        if (dp[ind][buy] != -1) {
            return dp[ind][buy];
        }
        int profit = 0;
        
        // We can buy the stock
        if (buy == 0) { 
            profit = Math.max(0 + func(ind + 1, 0, fee, n, arr, dp), (-1)*arr[ind] + func(ind + 1, 1, fee, n, arr, dp));
        }
        
        // We can sell the stock
        if (buy == 1) { 
            profit = Math.max(0 + func(ind + 1, 1, fee, n, arr, dp), arr[ind]-fee + func(ind + 1, 0, fee, n, arr, dp));
        }

        /* Store the value in dp array and
        return the calculated profit */
        return dp[ind][buy] = profit;
    }

    // Function to calculate the maximum profit earned 
    public int stockBuySell(int[] arr, int n, int fee) {
        if (n == 0) 
            return 0;
            
        // Declare a DP table to memoize results
        int[][] dp = new int[n][2];
        
        // Initialize the dp array with -1
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }

        int ans = func(0, 0, fee, n, arr, dp);
        
        // Return the maximum profit
        return ans;
    }

    public static void main(String[] args) {
        int n = 8;
        int[] arr = {3, 3, 5, 0, 0, 3, 1, 4};
        int fee = 1;
        
        // Create an instance of Solution class
        Solution sol = new Solution();

        // Call the stockBuySell function and print the result
        System.out.println("The maximum profit that can be generated is " + sol.stockBuySell(arr, n, fee));
    }
}
class Solution:
    # Function to find maximum profit earned using memoization
    def func(self, ind, buy, fee, n, arr, dp):
        # Base case 
        if ind == n:
            return 0
            
        """ If the result for this state has 
        already been calculated, return it"""
        if dp[ind][buy] != -1:
            return dp[ind][buy]
        
        profit = 0
        
        # We can buy the stock
        if buy == 0:
            profit = max(0 + self.func(ind + 1, 0, fee, n, arr, dp), (-1)*arr[ind] + self.func(ind + 1, 1, fee, n, arr, dp))
        
        # We can sell the stock
        if buy == 1:
            profit = max(0 + self.func(ind + 1, 1, fee, n, arr, dp), arr[ind]-fee + self.func(ind + 1, 0, fee, n, arr, dp))
        
        """ Store the value in dp array and
        return the calculated profit"""
        dp[ind][buy] = profit
        return dp[ind][buy]

    # Function to calculate the maximum profit earned 
    def stockBuySell(self, arr, n, fee):
        if n == 0:
            return 0
            
        """ Declare a 3D DP table with dimensions 
        (n) x 2 and initialize it with -1 """
        dp = [[-1 for _ in range(2)] for _ in range(n)]

        ans = self.func(0, 0, fee, n, arr, dp)
        
        # Return the maximum profit
        return ans

if __name__ == "__main__":
    n = 8
    arr = [3, 3, 5, 0, 0, 3, 1, 4]
    fee = 1
    
    # Create an instance of Solution class
    sol = Solution()

    # Call the stockBuySell function and print the result
    print("The maximum profit that can be generated is", sol.stockBuySell(arr, n, fee))
class Solution {
    // Function to find maximum profit earned using memoization
    func(ind, buy, fee, n, arr, dp) {
        // Base case 
        if (ind === n) {
            return 0;
        }
        /* If the result for this state has 
        already been calculated, return it*/
        if (dp[ind][buy] !== -1) {
            return dp[ind][buy];
        }
        let profit = 0;
        
        // We can buy the stock
        if (buy === 0) { 
            profit = Math.max(0 + this.func(ind + 1, 0, fee, n, arr, dp), (-1)*arr[ind] + this.func(ind + 1, 1, fee, n, arr, dp));
        }
        
        // We can sell the stock
        if (buy === 1) { 
            profit = Math.max(0 + this.func(ind + 1, 1, fee, n, arr, dp), arr[ind]-fee + this.func(ind + 1, 0, fee, n, arr, dp));
        }

        /* Store the value in dp array and
        return the calculated profit */
        dp[ind][buy] = profit;
        return dp[ind][buy];
    }

    // Function to calculate the maximum profit earned 
    stockBuySell(arr, n, fee) {
        if (n === 0) 
            return 0;
            
        // Initialize a DP table to memoize results
        const dp = new Array(n).fill(null).map(() =>
            new Array(2).fill(-1)
        );

        let ans = this.func(0, 0, fee, n, arr, dp);
        
        // Return the maximum profit
        return ans;
    }
}
    const n = 8;
    const arr = [3, 3, 5, 0, 0, 3, 1, 4];
    const fee = 1;
    
    // Create an instance of Solution class
    const sol = new Solution();

    // Call the stockBuySell function and print the result
    console.log("The maximum profit that can be generated is", sol.stockBuySell(arr, n, fee));

Complexity Analysis:

Time Complexity: O(N*2), There are N*2 states therefore at max ‘N*2’ new problems will be solved.

Space Complexity:O(N*2) + O(N), As we are using a recursion stack space(O(N)) and a 2D array ( O(N*2)).

In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:

Declare a dp array of size [n+1][2]: As there are two changing parameters in the recursive solution, 'ind' and 'buy'. The maximum value 'ind' can attain is (n) and including 0 its n+1, where n is the size of array, for 'buy' only two values possible 0, 1. So we need a 2D dp array.

Setting Base Cases in the Array: In the recursive code, our base condition was when If ind == n, it means we have finished trading on all days, and there is no more money that we can get, therefore we were simply returning 0, so here to set the base condition, we fill dp[n][0] = dp[n][1] = 0.

Iterative Computation Using Loops: Set two nested for loops, the outer loop (for variable 'ind') moves from n-1 to 0, as at index 'n', we have filled 0 for the base condition. The inner loop (for variable 'buy') moves from 0 to 1. In every iteration, apply the same logic as memoization and calculate the profits.

Choosing the maximum: As we are looking to maximize the profit earned, return the maximum value in all the cases as discussed in memoization approach.

Returning the answer: At last dp[0][0] maximum profit generated on ith day, for the top down approach.

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    //Function to find the maximum profit using tabulation
    int func(vector<int>& arr, int n, int fee) {
        
        /* Creating a 2D DP array of size 
        [n+1][2] initialized to 0*/
        vector<vector<int>> dp(n + 1, vector<int>(2, 0));

        /* Base case: dp array is already initialized
        to 0, covering the base case.*/

        // Iterate backwards through the prices array
        for (int ind = n - 1; ind >= 0; ind--) {
            
            // buy can be 0 (buying) or 1 (selling)
            for (int buy = 0; buy <= 1; buy++) {
                int profit;
                // We can buy the stock
                if (buy == 0) { 
                    profit = max(0 + dp[ind + 1][0],(-1)*arr[ind] + dp[ind + 1][1]);
                }
                // We can sell the stock
                if (buy == 1) { 
                    profit = max(0 + dp[ind + 1][1],arr[ind]-fee + dp[ind + 1][0]);
                }
                dp[ind][buy] = profit;
            }
        }

        /* The result is stored in dp[0][0] which
        represents maximum profit after final transaction.*/
        return dp[0][0];
    }
public:
    //Function to find the maximum profit
    int stockBuySell(vector<int> &arr, int n, int fee){
        //Return the answer
        return func(arr, n, fee);
    }
};

int main() {
    vector<int> prices = {3, 3, 5, 0, 0, 3, 1, 4};
    int n = prices.size();
    int fee = 1;

    // Create an instance of the Solution class
    Solution sol; 
    
    // Call the function and print the result
    cout << "The maximum profit that can be generated is " << sol.stockBuySell(prices, n, fee) << endl;

    return 0;
}
import java.util.*;

class Solution {
    // Function to find the maximum profit using tabulation
    private int func(int[] arr, int n, int fee) {
        /* Declaring a 2D DP array of 
        size [n+1][2] initialized to 0*/
        int[][] dp = new int[n + 1][2];

        /* Base case: dp array is already i
        nitialized to 0, covering the base case.*/

        // Iterate backwards through the prices array
        for (int ind = n - 1; ind >= 0; ind--) {
            
            // buy can be 0 (buying) or 1 (selling)
            for (int buy = 0; buy <= 1; buy++) {
                
                int profit = 0;
                // We can buy the stock
                if (buy == 0) { 
                    profit = Math.max(0 + dp[ind + 1][0],(-1)*arr[ind] + dp[ind + 1][1]);
                }
                // We can sell the stock
                if (buy == 1) { 
                    profit = Math.max(0 + dp[ind + 1][1],arr[ind]-fee + dp[ind + 1][0]);
                }
                dp[ind][buy] = profit;
            }
        }

        /* The result is stored in dp[0][0] which represents 
        maximum profit after the final transaction.*/
        return dp[0][0];
    }

    // Function to find the maximum profit
    public int stockBuySell(int[] arr, int n, int fee) {
        // Return the answer
        return func(arr, n, fee);
    }

    public static void main(String[] args) {
        int[] prices = {3, 3, 5, 0, 0, 3, 1, 4};
        int n = prices.length;
        int fee = 1;

        // Create an instance of the Solution class
        Solution sol = new Solution();

        // Call the function and print the result
        System.out.println("The maximum profit that can be generated is " + sol.stockBuySell(prices, n, fee));
    }
}
class Solution:
    # Function to find the maximum profit using tabulation
    def func(self, arr, n, fee):
        """ Declaring a 2D DP array of size 
        [n+1][2] initialized to 0"""
        dp = [[0 for _ in range(2)] for _ in range(n + 1)]

        """ Base case: dp array is already 
        initialized to 0, covering the base case."""

        # Iterate backwards through the prices array
        for ind in range(n - 1, -1, -1):
            
            # buy can be 0 (buying) or 1 (selling)
            for buy in range(2):
                
                # We can buy the stock
                if buy == 0:
                    dp[ind][buy] = max(0 + dp[ind + 1][0],
                                                (-1)*arr[ind] + dp[ind + 1][1])
                # We can sell the stock
                if buy == 1:
                    dp[ind][buy] = max(0 + dp[ind + 1][1],arr[ind]-fee + dp[ind + 1][0])

        """ The result is stored in dp[0][0] which 
        represents maximum profit after the final transaction."""
        return dp[0][0]

    # Function to find the maximum profit
    def stockBuySell(self, arr, n, fee):
        # Return the answer
        return self.func(arr, n, fee)

if __name__ == "__main__":
    prices = [3, 3, 5, 0, 0, 3, 1, 4]
    n = len(prices)
    fee = 1

    # Create an instance of the Solution class
    sol = Solution()

    # Call the function and print the result
    print("The maximum profit that can be generated is", sol.stockBuySell(prices, n, fee))
class Solution {
    // Function to find the maximum profit using tabulation
    func(arr, n, fee) {
        /* Declaring a 2D DP array of size
        [n+1][2] initialized to 0*/
        let dp = new Array(n + 1).fill().map(() => new Array(2).fill(0));

        /* Base case: dp array is already 
        initialized to 0, covering the base case.*/

        // Iterate backwards through the prices array
        for (let ind = n - 1; ind >= 0; ind--) {
            
            // buy can be 0 (buying) or 1 (selling)
            for (let buy = 0; buy <= 1; buy++) {
                // We can buy the stock
                if (buy === 0) { 
                    dp[ind][buy] = Math.max(0 + dp[ind + 1][0],(-1)*arr[ind] + dp[ind + 1][1]);
                }
                // We can sell the stock
                if (buy === 1) { 
                    dp[ind][buy] = Math.max(0 + dp[ind + 1][1],arr[ind]-fee + dp[ind + 1][0]);
                }
            }
        }

        /* The result is stored in dp[0][0] which
        represents maximum profit after the final transaction.*/
        return dp[0][0];
    }

    // Function to find the maximum profit
    stockBuySell(arr, n, fee) {
        
        // Return the answer
        return this.func(arr, n, fee);
    }
}

let prices = [3, 3, 5, 0, 0, 3, 1, 4];
let n = prices.length;
let fee = 1;

// Create an instance of the Solution class
let sol = new Solution();

// Call the function and print the result
console.log("The maximum profit that can be generated is " + sol.stockBuySell(prices, n, fee));

Complexity Analysis:

Time Complexity: O(N*2), As, here are three nested loops that account for O(N*2) complexity.

Space Complexity:O(N*2), As a 2D array of size N*2 is used.

If we observe the relation obtained in the tabulation, dp[ind][buy] = max( dp[ind+1][buy] , max( dp[ind+1][!buy]). we see that to calculate a value of a cell of the dp array, we need only the next column values(say ahead). So, we don’t need to store an entire 2-D array. Hence we can space optimize it.

The Steps to space optimize the tabulation approach are as follows:

First set the 'ahead' column as 0 for our base case, as we are starting from index 'n' and from the recursive code we know that index==n is our base case.

Then initialize three nested loops to calculate the 'cur' column values. Replace dp[ind] with 'cur' and dp[ind+1] with 'ahead' in our tabulation code.

After the inner loop execution, set 'ahead' as 'cur' for the next outer loop iteration. At last, return cur[0] as our answer.

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /*Function to find our maximum 
    profit using space optimization*/
    int func(vector<int>& arr, int n, int fee) {
        /* Create two 1D arrays to store profit information,
        one for current state and one for the ahead state.*/
        vector<int> ahead(2, 0);
        vector<int> cur(2, 0);

        // Iterate backwards through the prices array
        for (int ind = n - 1; ind >= 0; ind--) {
            
            // buy can be 0 (buying) or 1 (selling)
            for (int buy = 0; buy <= 1; buy++) {
                // We can buy the stock
                if (buy == 0) { 
                    cur[buy] = max(0 + ahead[0], -arr[ind] + ahead[1]);
                }
                // We can sell the stock
                if (buy == 1) { 
                    cur[buy] = max(0 + ahead[1], arr[ind]-fee + ahead[0]);
                }
            }
            /* Update the ahead state with the
            current state for the next iteration*/
            ahead = cur;
        }

        // Return the maximum profit 
        return cur[0];
    }
public:
    //Function to find out maximum profit
    int stockBuySell(vector<int> &arr, int n, int fee){
        //Return the answer
        return func(arr, n, fee);
    }
};

int main() {
    vector<int> prices = {3, 3, 5, 0, 0, 3, 1, 4};
    int n = prices.size();
    int fee = 1;

    // Create an instance of the Solution class
    Solution sol;

    // Call the funntion and print the result
    cout << "The maximum profit that can be generated is " << sol.stockBuySell(prices, n, fee) << endl;

    return 0;
}
import java.util.*;

class Solution {
    /* Function to find our maximum 
    profit using space optimization*/
    private int func(int[] arr, int n, int fee) {
        /* Declare two 1D arrays to store profit information,
        one for current state and one for the ahead state.*/
        int[] ahead = new int[2];
        int[] cur = new int[2];

        // Iterate backwards through the prices array
        for (int ind = n - 1; ind >= 0; ind--) {
            
            // buy can be 0 (buying) or 1 (selling)
            for (int buy = 0; buy <= 1; buy++) {
                // We can buy the stock
                if (buy == 0) {
                    cur[buy] = Math.max(0 + ahead[0],(-1)*arr[ind] + ahead[1]);
                }
                // We can sell the stock
                if (buy == 1) {
                    cur[buy] = Math.max(0 + ahead[1],arr[ind]-fee + ahead[0]);
                }
            }
            /* Update the ahead state with the 
            current state for the next iteration*/
            ahead = cur;
        }

        // Return the maximum profit 
        return cur[0];
    }

    // Function to find out maximum profit
    public int stockBuySell(int[] arr, int n, int fee) {
        // Return the answer
        return func(arr, n, fee);
    }

    public static void main(String[] args) {
        int[] prices = {3, 3, 5, 0, 0, 3, 1, 4};
        int n = prices.length;
        int fee = 1;

        // Create an instance of the Solution class
        Solution sol = new Solution();

        // Call the function and print the result
        System.out.println("The maximum profit that can be generated is " + sol.stockBuySell(prices, n, fee));
    }
}
class Solution:
    """ Function to find our maximum 
    profit using space optimization"""
    def func(self, arr, n, fee):
        """ Declare two 1D arrays to store profit information,
        one for current state and one for the ahead state."""
        ahead = [0, 0]
        cur = [0, 0]
        
        ahead[0] = ahead[1] = 0

        # Iterate backwards through the prices array
        for ind in range(n - 1, -1, -1):
            
            # buy can be 0 (buying) or 1 (selling)
            for buy in range(2):
                
                # We can buy the stock
                if buy == 0:
                    cur[buy] = max(0 + ahead[0], (-1)*arr[ind] + ahead[1])
                    
                # We can sell the stock
                if buy == 1:
                    cur[buy] = max(0 + ahead[1], arr[ind]-fee + ahead[0])
                    
            """ Update the ahead state with the 
            current state for the next iteration"""
            ahead = cur.copy()

        #Return the maximum profit
        return cur[0]

    # Function to find out maximum profit
    def stockBuySell(self, arr, n, fee):
        # Return the answer
        return self.func(arr, n, fee)

if __name__ == "__main__":
    prices = [3, 3, 5, 0, 0, 3, 1, 4]
    n = len(prices)
    fee = 1

    # Create an instance of the Solution class
    sol = Solution()

    # Call the function and print the result
    print("The maximum profit that can be generated is", sol.stockBuySell(prices, n, fee))
class Solution {
    /* Function to find our maximum 
    profit using space optimization*/
    func(arr, n, fee) {
        /* Create arrays 'ahead' and 'cur', 
        each initialized with two zeros*/
        let ahead = [0, 0];
        let cur = [0, 0];
    
        // Base condition: Initialize 'ahead' with zeros
        ahead[0] = ahead[1] = 0;

        // Iterate backwards through the prices array
        for (let ind = n - 1; ind >= 0; ind--) {
            
            // buy can be 0 (buying) or 1 (selling)
            for (let buy = 0; buy <= 1; buy++) {

                // We can buy the stock
                if (buy === 0) {
                    cur[buy] = Math.max(0 + ahead[0],-arr[ind] + ahead[1]);
                }
                // We can sell the stock
                if (buy == 1) {
                    cur[buy] = Math.max(0 + ahead[1],arr[ind]-fee + ahead[0]);
                }
            }
            /* Update the ahead state with the 
            current state for the next iteration*/
            ahead = cur;
        }

        // Return the maximum profit 
        return cur[0];
    }

    // Function to find out maximum profit
    stockBuySell(arr, n, fee) {
        // Return the answer
        return this.func(arr, n, fee);
    }
}
let prices = [3, 3, 5, 0, 0, 3, 1, 4];
let n = prices.length;
let fee = 1;

// Create an instance of the Solution class
let sol = new Solution();

// Call the function and print the result
console.log("The maximum profit that can be generated is " + sol.stockBuySell(prices, n, fee));

Complexity Analysis:

Time Complexity: O(N*2), As, here are three nested loops that account for O(N*2) complexity.

Space Complexity:O(1), As we are using two external arrays of size ‘2.

Problem List

Best time to buy and sell stock with transaction fees

Examples:

Constraints

Hints

Company Tags

Editorial

Steps to form the recursive solution:

Complexity Analysis:

Complexity Analysis:

The Steps to space optimize the tabulation approach are as follows:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts