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

## 20 comments on “Stock Buy Sell to Maximize Profit | GeeksforGeeks”

night ppl

In the "Interval" structure instance "sol", why has it been declared to have (n/2+1) elements? shouldn't just (n/2) suffice as buy and sell are always in pairs?

very helping.

How about iterating backwards?

I could solve it with just one loop.

public class Solution {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int size = scanner.nextInt();

for (int i = 0; i < size; i++) {

int numOfDays = scanner.nextInt();

int[] prices = new int[numOfDays];

for (int j = 0; j < numOfDays; j++) {

prices[j] = scanner.nextInt();

}

System.out.println(getMaxProfit(prices));

}

}

public static long getMaxProfit(int[] prices) {

long profit = 0L;

int maxSoFar = 0;

for (int i = prices.length – 1; i > -1 ; i–) {

if (prices[i] >= maxSoFar) {

maxSoFar = prices[i];

}

profit += maxSoFar – prices[i];

}

return profit;

}

}

one of the geeks article says that size of(arr)/ size of(arr[0]) will not provide no.of elements in that array but you people only using that logic.

this is just wrong. try 140 instead of 40. {100, 180, 260, 310, 140, 535, 695} – obviously the best strategy is to buy on day 0 and sell on last day.

How it will for {10, 22, 5, 75, 65, 80}

Here

local Minima | 10 | 5 | 65 |

Local Maxima | 22 | 75 | 80 |

Now how to choose two pairs?

The logic is to sell stock if the prices are falling next day. Then buy again next day and keep doing the same procedure. So if there is no local Maxima, max profit would be 0.

He is reading "f' instead of "s". "Processing" is "proffeffing"… LOL

This Solution is wrong for the input {1,2,3,4,5}.

Awesome explaination

Here in this code, you have meesed up both 2 if conditions. TO find the local minima, the current element should be smaller than the next element.But you wrote (if(i<n-1) && price[i]>price[i+1])..where it should be (if(i<n-1 && price[i]<price[i+1])) …and the same mistake for local maxima also. Please try to correct that mistake.

very flawed video

very well explained!

poor explanation

#include<bits/stdc++.h>

using namespace std;

int main()

{

int t,i,size,j,k=0,flag=0,a,b;

//cin>>t;

cin>>size;

int arr[size];

int brr[size];

for(i=0;i<size;i++)

{

cin>>arr[i];

}

for(i=1;i<size;i++)

{

if(flag==0)//search for minima

{

if(arr[i]>arr[i-1])

{

a=i-1;

flag=1;

continue;

}

}

if(flag==1)//for maxima

{

if(arr[i-1]<arr[i] && i+1==size)

{

b=i;

flag=0;

brr[k]=a;

k++;

brr[k]=b;

k++;

break;

}

if(arr[i-1]>arr[i])

{

b=i-1;

flag=0;

brr[k]=a;

k++;

brr[k]=b;

k++;

continue;

}

}

}

for(i=0;i<k;i=i+2)

{

printf("(%d %d)",brr[i],brr[i+1]);

}

return 0;

}

good video.

WTF! YOU ARE TYPING WHILE SAYING VERY IRRITATING NOICE…

how come the TC be o(n) if you are using while inside another while ?

if the number of transactions are given and there exists n number of local maxima and minima then??????????????