Stock Buy Sell to Maximize Profit | GeeksforGeeks
Stock Buy Sell to Maximize Profit | GeeksforGeeks
Explanation for the article: http://www.geeksforgeeks.org/stock-bu…
This video is contributed by Harshit Jain.
Content
0.59 -> Hello and welcome to GeeksForGeeks.
3.83 -> In this video we are going to solve the problem
titled “Stock buy sell to maximize profit”.
12.07 -> In this problem, we will be given the cost
of a stock on consecutive day.
17.77 -> We need to find the respective days on which
we should buy and then sell the stock to attain
24.02 -> maximum profit.
26.64 -> For example, let’s say the given array has
prices of stock as 100, 180, 260, 310, 40,
36.489 -> 535, and 695.
39.92 -> Here the price 100 is on day 0, 180 on day
1, 260 on day 2 and so on.
48.239 -> To attain the maximum profit, we should buy
and sell the stock twice.
52.35 -> Firstly, we will buy the stock on day 0 at
a price of 100 and sell on day 3 at a price
59.831 -> of 310.
62.69 -> Then again on day 4 we buy the stock at price
of 40 and then again sell it at a price of
69.409 -> 695 on day 6.
73.029 -> It is interesting to observe that if the prices
are sorted in decreasing order, then profit
78.659 -> cannot be earned at all as the price of stock
never increase.
83.679 -> So, let us start by looking at the algorithm
to solve this problem followed by a dry run
90.749 -> of the algorithm and finally walkthrough of
its implementation.
96.569 -> First step is to find the local minima and
store it as the starting index.
103.02 -> In our case the local minima would be the
first element which is smaller than it’s
107.68 -> next element.
110.229 -> Then we find the local maxima and store it
as ending index.
115.77 -> Local maxima will be an element which would
be greater than it’s next element.
121.959 -> Then we update the solution with these values.
125.52 -> So we would buy the stock on day of minima
and sell the stock on day of maxima.
132.18 -> We keep on repeating these steps until the
end of the array is reached.
138.23 -> Now let’s do a dry run of the algorithm.
141.989 -> So we are given this array having elements
100, 180, 260, 310, 40, 535 and 695.
151.11 -> We will be starting with the step 1 of our
algorithm which is to find the local minima
159.2 -> and store it as starting index.
161.76 -> So, we look at the first element of the array
i.e. 100.
167.68 -> We check if 100 is smaller than next element
i.e. 180?
171.609 -> Yes, it is.
173.62 -> So, 100 becomes the local minima.
178.329 -> Now we’ll proceed to step 2 i.e. find the
local maxima.
183.719 -> For that we compare the element 180 with next
element i.e. 260.
189.439 -> As 180 is not greater than 260, so we’ll
keep looking for local maxima.
196.159 -> Now we compare 260 with 310.
200.079 -> Again, as 260 isn’t greater than 310, so
we’ll keep looking for local maxima.
209.83 -> Now we compare 310 with 40.
213.629 -> As 310 is greater than 40, we have found the
local maxima i.e. 310.
221.92 -> Now we’ll again move to step 1 i.e. finding
the next local minima.
226.79 -> So, we compare 40 with 535.
230.099 -> As 40 < 535, we have found the local minima.
237.349 -> Now we’ll find the local maxima as per step
2 of the algorithm.
242.349 -> We compare 535 with 695.
246.18 -> As 535 is smaller than 695, 535 is not local
maxima and thus we’ll keep looking.
254.939 -> Now, 695 is the last element of the array,
thus it is the local maxima as per the algorithm.
262.599 -> So, we have found 2 pairs of minima and maxima.
266.91 -> Now to get the maximum profit one should buy
at 100 and sell at 310.
274.09 -> Then again buy at 40 and sell at 695.
280.199 -> Now let’s look at the implementation of
the algorithm.
283.71 -> Here we have defined a structure Interval
which contains two members namely buy and
289.84 -> sell both of which are of type integer.
294.24 -> They are going to store the respective days
at which one should buy and sell stock to
299.91 -> maximize the profit.
303.75 -> Now we see the function stockBuySell, which
takes as an argument the price array and integer
310.49 -> n where n is the size of the price array.
315.139 -> In this function, we first check that prices
should be given for at least 2 days.
320.84 -> Otherwise we return.
322.52 -> Then we create an array of type structure
Interval.
326.849 -> Its size is set as n/2+1 because that is the
maximum size that would be required in worst
333.44 -> case.
336.44 -> Then we declare a variable i and initialize
it as 0.
341.21 -> Then we run a loop, while i is smaller than
n-1.
348.36 -> So while i is smaller than n-1, that means,
elements are yet to be processed in the array.
355.47 -> Now, we try to find a local minima.
359.65 -> For that we run a while loop having the condition
that price of next element should be smaller
365.74 -> than current element.
367.58 -> Till the time this condition holds true, we
keep on incrementing the value of i.
374.33 -> Once we break out of the loop, we also check
if i has become equal to n-1, because if that
381.13 -> is the case, it means that there are no further
solutions possible and thus we should break
386.159 -> out of the loop.
387.31 -> Otherwise we store the index of our local
minima.
392.88 -> Now similarly, we’ll find out the local
maxima.
396 -> We run a while loop having condition that
price of current element should be greater
401.43 -> than previous element.
402.71 -> Till the time this condition holds true, we
keep on incrementing the value of i.
410.18 -> Once we break out of this loop, we save the
index of maxima as i-1.
413.539 -> We break out of the loop when previous element
is greater than current element.
420.509 -> Thus, local maxima is the previous element
instead of current element and thus we save
426.349 -> the index of maxima as i-1.
431.06 -> Then we finally increase the value of count
variable by 1.
437.29 -> Now we have the final value of the count variable.
440.159 -> If the value of the count variable is equal
to zero, it means that there is no day when
446.159 -> buying and selling the stocks will make a
profit.
449.509 -> Otherwise, we print the days on which profit
can be earned by buying and selling the stocks.
457.08 -> For that we run a for loop and print the buy
and sell values in the sol array.
464.3 -> Here is the driver method for this program.
467.099 -> Firstly, we have the price array.
470.75 -> Then we calculate the length of the array
by dividing the size of the array with the
475.03 -> size of the first element.
478.28 -> Then we just call the function StockBuySell
with price array and it’s size as arguments.
486.06 -> As far as time complexity is concerned, we
see that the outer loop runs till i becomes
491.38 -> n-1 and the inner loops just increment the
same value of i.
495.46 -> So, the overall time complexity comes out
to be O(n).
502.37 -> So, that is all for this tutorial.
505.09 -> Thank you.
Source: https://www.youtube.com/watch?v=JaosdXkUWTs