Maximum profit after buying and selling the stocks with transaction fees | Set 2
Given an array arr[] of positive integers representing prices of stocks and an integer transactionFee, the task is to find the maximum profit possible after buying and selling stocks any number of times and giving the transaction fee for each transaction.
Examples:
Input: arr[] = {6, 1, 7, 2, 8, 4}, transactionFee = 2
Output: 8
Explanation:
A maximum profit of 8 can be obtained by two transactions.
Transaction 1: Buy at price 1 and sell at price 7. Profit = 7 – 1 – 2 = 4.
Transaction 2: Buy at price 2 and sell at price 8. Profit = 8 – 2 – 2 = 4.
Therefore, total profit = 4 + 4 = 8, which is the maximum possible.Input: arr[] = {2, 7, 5, 9, 6, 4}, transactionFee = 1
Output: 7
Naive Approach: Refer to the previous post for the simplest approach to solve the problem.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Recursive Approach:
If we purchase at an index, we have the option to either sell or pass on the following index.
If we choose to sell, we will incur a transaction fee, but if we opt to pass, we can still sell or pass on
the next index. On the other hand, if we sell at an index, our only options are to buy or pass on the
next index and so on.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum // profit with transaction fee int f( int idx, int n, int buy, int prices[], int fee) { if (idx == n) { return 0; } int profit = 0; // you can either buy or not buy if (buy == 0) { profit = max(-prices[idx] + f(idx + 1, n, 1, prices, fee), f(idx + 1, n, 0, prices, fee)); } // you can either sell or not sell else { profit = max(prices[idx] - fee + f(idx + 1, n, 0, prices, fee), f(idx + 1, n, 1, prices, fee)); } return profit; } int MaxProfit( int prices[], int n, int fee) { return f(0, n, 0, prices, fee); } // Driver code int main() { // Given Input int arr[] = { 6, 1, 7, 2, 8, 4 }; int n = sizeof (arr) / sizeof (arr[0]); int transactionFee = 2; // Function Call cout << MaxProfit(arr, n, transactionFee); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to find the maximum profit with transaction // fee static int f( int idx, int n, int buy, int prices[], int fee) { if (idx == n) { return 0 ; } int profit = 0 ; // you can either buy or not buy if (buy == 0 ) { profit = Math.max( -prices[idx] + f(idx + 1 , n, 1 , prices, fee), f(idx + 1 , n, 0 , prices, fee)); } // you can either sell or not sell else { profit = Math.max( prices[idx] - fee + f(idx + 1 , n, 0 , prices, fee), f(idx + 1 , n, 1 , prices, fee)); } return profit; } static int MaxProfit( int prices[], int n, int fee) { return f( 0 , n, 0 , prices, fee); } public static void main(String[] args) { // Given Input int arr[] = { 6 , 1 , 7 , 2 , 8 , 4 }; int n = arr.length; int transactionFee = 2 ; // Function Call System.out.println( MaxProfit(arr, n, transactionFee)); } } // This code is contributed by karthik |
Python3
# Python program for the above approach # Function to find the maximum # profit with transaction fee def f(idx, n, buy, prices, fee): if idx = = n: return 0 profit = 0 # you can either buy or not buy if buy = = 0 : profit = max ( - prices[idx] + f(idx + 1 , n, 1 , prices, fee), f(idx + 1 , n, 0 , prices, fee)) # you can either sell or not sell else : profit = max (prices[idx] - fee + f(idx + 1 , n, 0 , prices, fee), f(idx + 1 , n, 1 , prices, fee)) return profit def MaxProfit(prices, n, fee): return f( 0 , n, 0 , prices, fee) # Driver code if __name__ = = '__main__' : # Given Input arr = [ 6 , 1 , 7 , 2 , 8 , 4 ] n = len (arr) transactionFee = 2 # Function Call print (MaxProfit(arr, n, transactionFee)) |
C#
// C# program for the above approach using System; public class GFG { // Function to find the maximum profit with transaction // fee static int f( int idx, int n, int buy, int [] prices, int fee) { if (idx == n) { return 0; } int profit = 0; // you can either buy or not buy if (buy == 0) { profit = Math.Max( -prices[idx] + f(idx + 1, n, 1, prices, fee), f(idx + 1, n, 0, prices, fee)); } // you can either sell or not sell else { profit = Math.Max( prices[idx] - fee + f(idx + 1, n, 0, prices, fee), f(idx + 1, n, 1, prices, fee)); } return profit; } static int MaxProfit( int [] prices, int n, int fee) { return f(0, n, 0, prices, fee); } static public void Main() { // Code // Given Input int [] arr = { 6, 1, 7, 2, 8, 4 }; int n = arr.Length; int transactionFee = 2; // Function Call Console.WriteLine( MaxProfit(arr, n, transactionFee)); } } // This code is contributed by sankar. |
Javascript
// JavaScript program for the above approach // Function to find the maximum profit with transaction fee function f(idx, n, buy, prices, fee) { if (idx == n) { return 0; } let profit = 0; // you can either buy or not buy if (buy == 0) { profit = Math.max(-prices[idx] + f(idx + 1, n, 1, prices, fee), f(idx + 1, n, 0, prices, fee)); } // you can either sell or not sell else { profit = Math.max(prices[idx] - fee + f(idx + 1, n, 0, prices, fee), f(idx + 1, n, 1, prices, fee)); } return profit; } function maxProfit(prices, fee) { const n = prices.length; return f(0, n, 0, prices, fee); } // Given Input const arr = [6, 1, 7, 2, 8, 4]; const transactionFee = 2; // Function Call console.log(maxProfit(arr, transactionFee)); // This code is contributed by sankar. |
8
Time complexity: O(2^N), where n is the number of elements in the input array “prices”. This is because for each index, the function has two possibilities (buy or not buy, or sell or not sell) and it calls itself recursively for each possibility.
Auxiliary Space: O(N) Recursive Stack Space
Memoization Approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum // profit with transaction fee int f( int idx, int n, int buy, int prices[], vector<vector< int > >& dp, int fee) { if (idx == n) { return 0; } if (dp[idx][buy] != -1) { return dp[idx][buy]; } int profit = 0; // you can either buy or not buy if (buy == 0) { dp[idx][buy] = profit = max(-prices[idx] + f(idx + 1, n, 1, prices, dp, fee), f(idx + 1, n, 0, prices, dp, fee)); } // you can either sell or not sell else { dp[idx][buy] = profit = max(prices[idx] - fee + f(idx + 1, n, 0, prices, dp, fee), f(idx + 1, n, 1, prices, dp, fee)); } return profit; } int MaxProfit( int prices[], int n, int fee) { vector<vector< int > > dp(n, vector< int >(2, -1)); return f(0, n, 0, prices, dp, fee); } // Driver code int main() { // Given Input int arr[] = { 6, 1, 7, 2, 8, 4 }; int n = sizeof (arr) / sizeof (arr[0]); int transactionFee = 2; // Function Call cout << MaxProfit(arr, n, transactionFee); return 0; } |
Java
import java.util.*; public class Main { // Function to find the maximum // profit with transaction fee public static int f( int idx, int n, int buy, int [] prices, List<List<Integer>> dp, int fee) { if (idx == n) { return 0 ; } if (dp.get(idx).get(buy) != - 1 ) { return dp.get(idx).get(buy); } int profit = 0 ; // you can either buy or not buy if (buy == 0 ) { dp.get(idx).set(buy, profit = Math.max(-prices[idx] + f(idx + 1 , n, 1 , prices, dp, fee), f(idx + 1 , n, 0 , prices, dp, fee))); } // you can either sell or not sell else { dp.get(idx).set(buy, profit = Math.max(prices[idx] - fee + f(idx + 1 , n, 0 , prices, dp, fee), f(idx + 1 , n, 1 , prices, dp, fee))); } return profit; } public static int MaxProfit( int [] prices, int n, int fee) { List<List<Integer>> dp = new ArrayList<>(); for ( int i = 0 ; i < n; i++) { dp.add( new ArrayList<>(Arrays.asList(- 1 , - 1 ))); } return f( 0 , n, 0 , prices, dp, fee); } public static void main(String[] args) { // Given Input int [] arr = { 6 , 1 , 7 , 2 , 8 , 4 }; int n = arr.length; int transactionFee = 2 ; // Function Call System.out.println(MaxProfit(arr, n, transactionFee)); } } |
Python
def maxProfit(prices, fee): n = len (prices) dp = [[ 0 ] * 2 for _ in range (n)] # Initialize the base case dp[ 0 ][ 0 ] = 0 dp[ 0 ][ 1 ] = - prices[ 0 ] for i in range ( 1 , n): # Either do nothing (no transaction) or sell a stock (1 transaction) dp[i][ 0 ] = max (dp[i - 1 ][ 0 ], dp[i - 1 ][ 1 ] + prices[i] - fee) # Either do nothing (no transaction) or buy a stock (1 transaction) dp[i][ 1 ] = max (dp[i - 1 ][ 1 ], dp[i - 1 ][ 0 ] - prices[i]) # The final maximum profit is when you have no stock return dp[n - 1 ][ 0 ] # Given Input prices = [ 6 , 1 , 7 , 2 , 8 , 4 ] transaction_fee = 2 # Function Call print (maxProfit(prices, transaction_fee)) |
C#
using System; class Program { // Function to calculate maximum profit with transaction fee static int MaxProfit( int [] prices, int fee) { int n = prices.Length; int [,] dp = new int [n, 2]; // Initialize the dp array with -1 values for ( int i = 0; i < n; i++) { for ( int j = 0; j < 2; j++) { dp[i, j] = -1; } } // Call the recursive function to compute maximum profit return F(0, n, 0, prices, dp, fee); } // Recursive function to calculate maximum profit static int F( int idx, int n, int buy, int [] prices, int [,] dp, int fee) { // If we reach the end of the array, return 0 profit if (idx == n) { return 0; } // If the result for this state is already computed, return it if (dp[idx, buy] != -1) { return dp[idx, buy]; } int profit = 0; // If we are in a "buy" state (buying a stock), we can choose to buy or not buy if (buy == 0) { dp[idx, buy] = profit = Math.Max(-prices[idx] + F(idx + 1, n, 1, prices, dp, fee), F(idx + 1, n, 0, prices, dp, fee)); } // If we are in a "sell" state (selling a stock), we can choose to sell or not sell else { dp[idx, buy] = profit = Math.Max(prices[idx] - fee + F(idx + 1, n, 0, prices, dp, fee), F(idx + 1, n, 1, prices, dp, fee)); } return profit; } // Driver code static void Main() { int [] arr = { 6, 1, 7, 2, 8, 4 }; int transactionFee = 2; // Call the MaxProfit function to get the maximum profit int maxProfit = MaxProfit(arr, transactionFee); Console.WriteLine(maxProfit); } } |
Javascript
// Function to find the maximum profit with a transaction fee function maxProfit(prices, fee) { const n = prices.length; const dp = new Array(n).fill().map(() => new Array(2).fill(-1)); // Recursive function to calculate the maximum profit function f(idx, buy) { if (idx === n) { return 0; } if (dp[idx][buy] !== -1) { return dp[idx][buy]; } let profit = 0; if (buy === 0) { // If not holding a stock, choose to either buy or do nothing dp[idx][buy] = profit = Math.max( -prices[idx] + f(idx + 1, 1), // Buy a stock f(idx + 1, 0) // Do nothing ); } else { // If holding a stock, choose to either sell or do nothing dp[idx][buy] = profit = Math.max( prices[idx] - fee + f(idx + 1, 0), // Sell the stock f(idx + 1, 1) // Do nothing (keep the stock) ); } return profit; } return f(0, 0); } // Driver code function main() { // Given Input const arr = [6, 1, 7, 2, 8, 4]; const transactionFee = 2; // Function Call console.log(maxProfit(arr, transactionFee)); } main(); |
8
Time Complexity: O(N)
Space Complexity: O(N)
Efficient Approach: To optimize the above approach, the idea is to use Dynamic Programming. For each day, maintain the maximum profit, if stocks are bought on that day (buy) and the maximum profit if all stocks are sold on that day (sell). For each day, update buy and sell using the following relations:
buy = max(sell – arr[i], buy)
sell = max(buy +arr[i] – transactionFee, sell)
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum // profit with transaction fee int MaxProfit( int arr[], int n, int transactionFee) { int buy = -arr[0]; int sell = 0; // Traversing the stocks for // each day for ( int i = 1; i < n; i++) { int temp = buy; // Update buy and sell buy = max(buy, sell - arr[i]); sell = max(sell, temp + arr[i] - transactionFee); } // Return the maximum profit return max(sell, buy); } // Driver code int main() { // Given Input int arr[] = { 6, 1, 7, 2, 8, 4 }; int n = sizeof (arr) / sizeof (arr[0]); int transactionFee = 2; // Function Call cout << MaxProfit(arr, n, transactionFee); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to find the maximum // profit with transaction fee static int MaxProfit( int arr[], int n, int transactionFee) { int buy = -arr[ 0 ]; int sell = 0 ; // Traversing the stocks for // each day for ( int i = 1 ; i < n; i++) { int temp = buy; // Update buy and sell buy = Math.max(buy, sell - arr[i]); sell = Math.max(sell, temp + arr[i] - transactionFee); } // Return the maximum profit return Math.max(sell, buy); } // Driver code public static void main(String[] args) { // Given Input int arr[] = { 6 , 1 , 7 , 2 , 8 , 4 }; int n = arr.length; int transactionFee = 2 ; // Function Call System.out.println( MaxProfit(arr, n, transactionFee)); } } // This code is contributed by Potta Lokesh |
Python3
# Python3 program for the above approach # Function to find the maximum # profit with transaction fee def MaxProfit(arr, n, transactionFee): buy = - arr[ 0 ] sell = 0 # Traversing the stocks for # each day for i in range ( 1 , n, 1 ): temp = buy # Update buy and sell buy = max (buy, sell - arr[i]) sell = max (sell, temp + arr[i] - transactionFee) # Return the maximum profit return max (sell, buy) # Driver code if __name__ = = '__main__' : # Given Input arr = [ 6 , 1 , 7 , 2 , 8 , 4 ] n = len (arr) transactionFee = 2 # Function Call print (MaxProfit(arr, n, transactionFee)) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approach using System; class GFG { // Function to find the maximum // profit with transaction fee static int MaxProfit( int [] arr, int n, int transactionFee) { int buy = -arr[0]; int sell = 0; // Traversing the stocks for // each day for ( int i = 1; i < n; i++) { int temp = buy; // Update buy and sell buy = Math.Max(buy, sell - arr[i]); sell = Math.Max(sell, temp + arr[i] - transactionFee); } // Return the maximum profit return Math.Max(sell, buy); } // Driver code public static void Main() { // Given Input int [] arr = { 6, 1, 7, 2, 8, 4 }; int n = arr.Length; int transactionFee = 2; // Function Call Console.WriteLine( MaxProfit(arr, n, transactionFee)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript program for the above approach // Function to find the maximum // profit with transaction fee function MaxProfit(arr, n, transactionFee) { let buy = -arr[0]; let sell = 0; // Traversing the stocks for // each day for (let i = 1; i < n; i++) { let temp = buy; // Update buy and sell buy = Math.max(buy, sell - arr[i]); sell = Math.max(sell, temp + arr[i] - transactionFee); } // Return the maximum profit return Math.max(sell, buy); } // Driver Code // Given Input let arr = [ 6, 1, 7, 2, 8, 4 ]; let n = arr.length; let transactionFee = 2; // Function Call document.write( MaxProfit(arr, n, transactionFee)); // This code is contributed by sanjoy_62 </script> |
8
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us