Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation
3.
Dynamic Programming Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
C++ Implementation
3.4.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Divide and Conquer Approach
4.1.
Algorithm
4.2.
Dry Run
4.2.1.
Left Side Profits
4.2.2.
Right Side Profits
4.2.3.
Overall Maximum Profit
4.3.
C++ Implementation
4.4.
Output
4.5.
Time Complexity
4.6.
Space Complexity
5.
Frequently Asked Questions
5.1.
What is a dynamic programming approach?
5.2.
Why is dynamic programming more efficient than recursion?
5.3.
Which algorithm is better among dynamic programming and backtracking?
5.4.
What is the divide and conquer algorithm?
5.5.
What are the limitations of the divide-and-conquer approach?
6.
Conclusion
Last Updated: Mar 27, 2024
Hard

Best Time to Buy and Sell Stock III

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Hello Ninjas! Stock Market is all about making profits. We must strategize the time when we buy and sell stocks to gain maximum profits. Combining this real-world trading scenario with programming, we will be solving an exciting problem; the Best Time to Buy and Sell Stock III. This problem is a variation of Best Time to Buy and Sell Stock and Best Time to Buy and Sell Stock II. You can try them before solving this problem.

Best Time to Buy and Sell Stock III

We will be looking at different approaches, their dry run, and their complexities. Let's begin by understanding the problem statement in depth.

Problem Statement

The problem states that you are given the stock prices for days, which are represented by an array stocks. Your task is to earn the maximum profit by buying and selling stocks, but you can only buy and sell for a maximum of two times.

Also, you are not allowed to do multiple transactions at the same time, which means you cannot buy a stock before you sell the stock you are holding. Find the maximum profit that you can earn.

Example

Input

n = 7
stocks = [3, 8, 2, 1, 6, 9, 2]

Where n is the number of days and stocks represents the array of prices.

Output

13

Explanation

We can buy the stock on 1st day at the price of 3 and sell the stock on 2nd day for 8. This will make a profit of 8-3, i.e., 5. Now purchase the stock on the 4th day and sell it on the second last day, making a profit of 8. So the total profit adds up to 8+5 = 13.

Explanation

Please try to solve this problem on your own before moving on to further discussion.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 ith 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.

dry run

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

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 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 3rd day. Now, the maximum profit left can be made by buying on the 1st day and selling on the 2nd day. Similarly, the maximum profit on the right side can be made by buying on the 4th day and selling on the 6th day.

Divide and Conquer Approach

If we check this one by one for each index, the complexity of the solution will be O(n2), 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.

left_profit array

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

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

Index 1

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

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

index 2

Similarly, this can be done for the remaining indexes.

Right Side Profits

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

right_profit array

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

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

index 5

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

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

index 4

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.

left_profit and right_profit arrays

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

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:

 

You may refer to our Guided Path on Code Studios for enhancing your skill set on DSACompetitive ProgrammingSystem 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!

Previous article
Best time to buy and sell stock II
Next article
Best Time to Buy and Sell Stock with at most K Transactions
Live masterclass