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.

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 n 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 1^{st} day at the price of 3 and sell the stock on 2^{nd} day for 8. This will make a profit of 8-3, i.e., 5. Now purchase the stock on the 4^{th} day and sell it on the second last day, making a profit of 8. So the total profit adds up to 8+5 = 13.

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

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^{2}), 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.

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: