Best Time to Buy and Sell Stock III

Dynamic Programming Approach

We can solve this problem using recursion. If we observe carefully, we can see that we have three options each day: buy, sell, or just skip that particular day.

Let's first discuss the three scenarios:

• BUY: To buy the stock; we have to check two conditions. First, we shouldn't be holding any stock, and second, the limit of trading, i.e., 2 in this case, should not have been reached.
   
• SELL: If you want to sell the stock, you must hold a stock that you can sell. So we have to check only that condition.
   
• SKIP: We can skip the trade on any day, i.e., we can decide to neither buy nor sell on that day. We don't have to check any conditions for this.
   

We will apply this logic, and with the help of a DP array, we will store the results for the subproblems and reuse the results to find the solution to the larger problem. The algorithm for the memorization approach is written below.

Algorithm

• Initialize a 3-D array with three variables: the index, which represents the i^th day, a variable can_buy to track if we are holding any stock or not; and the trade_limit to ensure we perform only two trades.
   
• Call for the function which returns the maximum profit and passes the index as 0, can_buy as 1 ( since we aren't holding any stock ), trade_limit as 2 and the DP array.
   
• The trade function will recursively find the solutions by calling the function for sub-problems until the index becomes equal to the size of the prices array, stocks, or trade_limit = 0. 
   
• Check if the solution for the current scenario already exists; if yes, then return the solution using the DP array.
   
• Else, we can perform 3 operations, buy, sell, or skip:
  
  
  • If can_buy is equal to 1, the profit will be equal to -stocks[ index ] + f (index+1), as the amount is spent in buying, and we will call for further index by passing index+1 in the trade function. Set the can_buy as 0.
     
  • Else, we are holding stock, and we can only sell it. The profit will be equal to stocks[ index ] + f (index+1). Mark the can_buy as 1, and decrement the trade_limit.
     
  • We can skip the day, and the profit will be f (index+1). The trade_limit and can_buy will remain the same.
     
• The profit will be the maximum of three; store it in the DP array and return the profit.

Dry Run

The array of the prices is given as stocks = [3, 8, 2, 1, 6, 9, 2]. Initialy the can_buy = 1, and trade_limit = 2. Let's see the function call for index = 0.

At index = 0, we have two choices: buy or skip. If we perform a buy operation, the profit will be -3 + f ( index+1 ). The can_buy will become 0, as we are now holding stock. If we skip the operations, the profit will be f ( index+1 ).

The above operations will call for index = 1. Now when can_buy = 0. We can either sell the stock or skip it. If we perform the sell operation, profit will be 8 + f ( index+1 ), can_buy will be set to 1, and trade_limit will decrement.

 

This way, the function calls will work until the base condition is reached. Let's now see the C++ implementation for the same.

C++ Implementation

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

// recursive function
int trade(vector<int> &stocks, int index, int can_buy, int trade_limit, vector<vector<vector<int>>> &dp) {
	// base condition
	if (index == stocks.size() || trade_limit == 0) return 0;

	// stored result of sub-problem
	if (dp[index][can_buy][trade_limit] != -1)
		return dp[index][can_buy][trade_limit];

	int buy = 0, sell = 0, skip = 0;
   
	// buy transaction
	if (can_buy) {
		buy = -stocks[index] + trade(stocks, index + 1, 0, trade_limit, dp);
	}
	// sell transaction
	else {
		sell = stocks[index] + trade(stocks, index + 1, 1, trade_limit - 1, dp);
	}
	
	// skip
	skip = trade(stocks, index + 1, can_buy, trade_limit, dp);

	// store the result
	return dp[index][can_buy][trade_limit] = max(buy, max(sell, skip));
}
int main() {
	int n = 7;
	vector<int> stocks = {3, 8, 2, 1, 6, 9, 2};

	// 3-d dp
	vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(3, -1)));

	cout << "The maximum profit is: " << trade(stocks, 0, 1, 2, dp);
	return 0;
}

Output

Time Complexity

The time complexity for this approach is O(n) because there is the possibility of maximum n*2*3 problems, as there are n stocks, and for each day value of can_buy can be 0 or 1. Also, the maximum value of trade_limit is 2, so an array of size 3 is required for it.

Space Complexity

The space complexity of the above solution is O(n), as we have used a recursion stack space O(n) and a 3-D array to store the solutions (O(n*2*3)).

Check out this problem - Minimum Coin Change Problem 

Divide and Conquer Approach

We can also use Divide and Conquer algorithm to solve this problem. For each index, we will divide the array into 2 parts; we have to find the maximum profit that can be made if we perform 1 transaction on the left side and another on the right side.

Suppose we have divided the array around 3^rd day. Now, the maximum profit left can be made by buying on the 1^st day and selling on the 2^nd day. Similarly, the maximum profit on the right side can be made by buying on the 4^th day and selling on the 6^th day.

If we check this one by one for each index, the complexity of the solution will be O(n²), which can be reduced to O(n) by the use of two arrays:

• The left array is used to store the maximum profit we can make till the current day. It will be filled by traversing the array from left to right.
   
•  The right array is also used to store the maximum profit, but it will be filled from right to left; this will give the profits from the right part of the array.
   

Finally, the maximum profit will be found by maximizing the sum of the profits on the left side and right side for each day.

Algorithm

• Initialize two arrays, left_profit and right_profit. They will be used to store the maximum profits on the left and right sides for each day.
   
• Take two variables, left_mini = stocks[0] and right_maxi = stocks[ n-1 ], which will be used to maintain the minimum price till now from the left side and the maximum price till now from the right side, respectively.
   
• Traverse from index = 1 to n-1, and for each index, perform the following steps:
  
  
  • left_profit[ i ] = max( left_profit[ i-1 ], stocks[ i ] - left_mini ), this is used to store the maximum profit till now, which can be found by taking the maximum of maximum profit till previous index and profit if we sell the stock at the current price.
     
  • left_mini = min( left_mini, stocks[i] ), it’s used to minimize the buy price.
     
• Traverse from index = n-2 to 0, and for each index, perform the following steps:
  
  
  • right_profit[ i ] = max( right_profit[ i+1 ], right_maxi - stocks[ i ]), this is used to store the maximum profit from the right side if we sell the stock at the current price. It is found by taking maximum of maximum profit till index + 1 and profit if we buy the stock at the current price.
     
  • right_maxi = max( right_maxi, stocks[ i ] ), it is used to maximize the selling price.
     
• Calculate the overall maximum profit by calculating the maximum profit at each step. For current index maximum profit = left_profit[ i-1 ] + right_profit[ i ].

Dry Run

First, create the left_profit and right_profit arrays. Let’s look at how it can be done for a few indexes.

Left Side Profits

Initially, the array looks like this, and left_mini = 3.

Now, for index = 1, stocks[ i ] = 8 and left_profit[ 0 ] = 0.

left_profit [ 1 ] = max( 0 , 8 - 3 ) = 5

For index = 2, stocks[ i ] = 2 and left_profit[ 1 ] = 5.

left_profit[ 2 ] = max( 5 , 2 - 3 ) = 5. Update left_mini = 2.

Similarly, this can be done for the remaining indexes.

Right Side Profits

Initially, the array looks like this, and right_maxi = 2.

Now, for index = 5, stocks[ i ] = 9 and right_profit[ 6 ] = 0.

right_profit[ 5 ] = max( 0 , 2 - 9 ) = 0. Update right_maxi = 9.

Now, for index = 4, stocks[ i ] = 6 and right_profit[ 5 ] = 0.

right_profit[ 4 ] = max( 0, 9 - 6 ) = 3.

Similarly, this can be done for the remaining indexes.

Overall Maximum Profit

After completing the iterations, the left_profit and right_profit arrays look like this.

Now Initially profit = max( 8, 8 ) = 8.

For index = 1, left_profit[ i - 1 ] = 0 and right_profit[ i ] = 8

profit = max( profit, 0 + 8 ) = 8.

 

For index = 2, left_profit[ i - 1 ] = 5 and right_profit[ i ] = 8

profit = max( profit, 5 + 8 ) = 13.

 

Similarly, we can calculate for other indexes, and we will get the overall maximum profit.

C++ Implementation

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

int main()
{
	int n = 7;
	vector<int> stocks = {3, 8, 2, 1, 6, 9, 2};

	int profit = -1e9;

	/*
		For storing maximum profits on the left and right side
	*/
	vector<int> left_profit(n, 0);
	vector<int> right_profit(n, 0);

	int left_mini = stocks[0], right_maxi = stocks[n-1];

	// Left to right
	for(int i=1; i<n; i++){
		left_profit[i] = max(left_profit[i-1], stocks[i] - left_mini);
 		left_mini = min(left_mini, stocks[i]);
	}

	// Right to left
	for(int i=n-2; i>=0; i--){
		right_profit[i] = max(right_profit[i+1], right_maxi - stocks[i]);
		right_maxi = max(right_maxi, stocks[i]);
	}
   
	// Finding overall profit
	profit = max(left_profit[n-1], right_profit[0]);
	for(int i=1; i<n-1; i++){
		profit = max(profit, left_profit[i-1]+right_profit[i]);
	}
	
	cout << "The maximum profit is: " << profit ;
	return 0;
}

Output

Time Complexity

The time complexity for this approach is O(n) because each loop is traversing the array of prices whose size is n.

Space Complexity

The space complexity of the adobe solution is O(n), as we have created two extra arrays, left and right side, so the space taken = O( n + n + n) = O( 3n ).

Frequently Asked Questions

What is a dynamic programming approach?

The dynamic programming approach is used to solve problems by dividing them down into smaller subproblems and solving each subproblem only once. The result of subproblems is used to avoid redundant work.

Why is dynamic programming more efficient than recursion?

Dynamic programming is more efficient than recursion because it reduces redundancy by storing the solutions to subproblems. While in recursion, the same subproblem is solved multiple times, which leads to more time and space complexity.

Which algorithm is better among dynamic programming and backtracking?

The efficiency of both algorithms depends on the type of problem. Dynamic programming is best for problems with recursive structures and overlapping subproblems, whereas backtracking is efficient for problems with many potential solutions.

What is the divide and conquer algorithm?

The divide-and-conquer algorithm is used to solve problems by breaking them down into smaller subproblems that are easier to solve and then combining the results of those subproblems to solve the larger problem.

What are the limitations of the divide-and-conquer approach?

The divide-and-conquer approach is less efficient for solving smaller problems. For problems where the subproblems have a lot of overlapping solutions, the divide-and-conquer approach may not be the most efficient method.

Conclusion

This article discussed an important question, the Best Time to Buy and Sell Stock III. We have seen different approaches for the same. We also discussed the dry run and algorithm, along with the time and space complexities.

To solve more such problems, you can check out our other blogs:

• Best Time to Buy and Sell Stock
• Best Time to Buy and Sell Stock II
• Best Time to Buy and Sell Stock IV
• 0- 1 Knapsack
• Longest Common Subsequence

 

You may refer to our Guided Path on Code Studios for enhancing your skill set on DSA, Competitive Programming, System Design, etc. Check out essential interview questions, practice our available mock tests, look at the interview bundle for interview preparations, and so much more!

Happy Learning, Ninjas!