Stock Buy Sell to Maximize Profit | GeeksforGeeks - YouTube

Hello and welcome to GeeksForGeeks.

In this video we are going to solve the problem titled “Stock buy sell to maximize profit”.

In this problem, we will be given the cost of a stock on consecutive day.

We need to find the respective days on which we should buy and then sell the stock to attain

maximum profit.

For example, let’s say the given array has prices of stock as 100, 180, 260, 310, 40,

535, and 695.

Here the price 100 is on day 0, 180 on day 1, 260 on day 2 and so on.

To attain the maximum profit, we should buy and sell the stock twice.

Firstly, we will buy the stock on day 0 at a price of 100 and sell on day 3 at a price

of 310.

Then again on day 4 we buy the stock at price of 40 and then again sell it at a price of

695 on day 6.

It is interesting to observe that if the prices are sorted in decreasing order, then profit

cannot be earned at all as the price of stock never increase.

So, let us start by looking at the algorithm to solve this problem followed by a dry run

of the algorithm and finally walkthrough of its implementation.

First step is to find the local minima and store it as the starting index.

In our case the local minima would be the first element which is smaller than it’s

next element.

Then we find the local maxima and store it as ending index.

Local maxima will be an element which would be greater than it’s next element.

Then we update the solution with these values.

So we would buy the stock on day of minima and sell the stock on day of maxima.

We keep on repeating these steps until the end of the array is reached.

Now let’s do a dry run of the algorithm.

So we are given this array having elements 100, 180, 260, 310, 40, 535 and 695.

We will be starting with the step 1 of our algorithm which is to find the local minima

and store it as starting index.

So, we look at the first element of the array i.e. 100.

We check if 100 is smaller than next element i.e. 180?

Yes, it is.

So, 100 becomes the local minima.

Now we’ll proceed to step 2 i.e. find the local maxima.

For that we compare the element 180 with next element i.e. 260.

As 180 is not greater than 260, so we’ll keep looking for local maxima.

Now we compare 260 with 310.

Again, as 260 isn’t greater than 310, so we’ll keep looking for local maxima.

Now we compare 310 with 40.

As 310 is greater than 40, we have found the local maxima i.e. 310.

Now we’ll again move to step 1 i.e. finding the next local minima.

So, we compare 40 with 535.

As 40 < 535, we have found the local minima.

Now we’ll find the local maxima as per step 2 of the algorithm.

We compare 535 with 695.

As 535 is smaller than 695, 535 is not local maxima and thus we’ll keep looking.

Now, 695 is the last element of the array, thus it is the local maxima as per the algorithm.

So, we have found 2 pairs of minima and maxima.

Now to get the maximum profit one should buy at 100 and sell at 310.

Then again buy at 40 and sell at 695.

Now let’s look at the implementation of the algorithm.

Here we have defined a structure Interval which contains two members namely buy and

sell both of which are of type integer.

They are going to store the respective days at which one should buy and sell stock to

maximize the profit.

Now we see the function stockBuySell, which takes as an argument the price array and integer

n where n is the size of the price array.

In this function, we first check that prices should be given for at least 2 days.

Otherwise we return.

Then we create an array of type structure Interval.

Its size is set as n/2+1 because that is the maximum size that would be required in worst

case.

Then we declare a variable i and initialize it as 0.

Then we run a loop, while i is smaller than n-1.

So while i is smaller than n-1, that means, elements are yet to be processed in the array.

Now, we try to find a local minima.

For that we run a while loop having the condition that price of next element should be smaller

than current element.

Till the time this condition holds true, we keep on incrementing the value of i.

Once we break out of the loop, we also check if i has become equal to n-1, because if that

is the case, it means that there are no further solutions possible and thus we should break

out of the loop.

Otherwise we store the index of our local minima.

Now similarly, we’ll find out the local maxima.

We run a while loop having condition that price of current element should be greater

than previous element.

Till the time this condition holds true, we keep on incrementing the value of i.

Once we break out of this loop, we save the index of maxima as i-1.

We break out of the loop when previous element is greater than current element.

Thus, local maxima is the previous element instead of current element and thus we save

the index of maxima as i-1.

Then we finally increase the value of count variable by 1.

Now we have the final value of the count variable.

If the value of the count variable is equal to zero, it means that there is no day when

buying and selling the stocks will make a profit.

Otherwise, we print the days on which profit can be earned by buying and selling the stocks.

For that we run a for loop and print the buy and sell values in the sol array.

Here is the driver method for this program.

Firstly, we have the price array.

Then we calculate the length of the array by dividing the size of the array with the

size of the first element.

Then we just call the function StockBuySell with price array and it’s size as arguments.

As far as time complexity is concerned, we see that the outer loop runs till i becomes

n-1 and the inner loops just increment the same value of i.

So, the overall time complexity comes out to be O(n).

So, that is all for this tutorial.

Thank you.