Stock Buy Sell to Maximize Profit | GeeksforGeeks


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

  1. 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?

  2. 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;
    }

    }

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

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

  5. 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?

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

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

  8. #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;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *