Sunday, July 7, 2019

Stock Buy & Sell Problem


Question: There is a given array of the stock price, each index denotes the price of the stock on that day. You need to find the max profit you will earn if you buy and sell the stock.




Example - Given an array - [10,5,6,8,9,3] where index 0 shows the prices of the stock on day 1 respectively.

Answer   Maxprofit=4
Explanation - first, we purchase at day 2 ( price - 5) and sell at day 5 (price 9 ) profit = 9-5=4


Code - 

package com.vp.learning;

public class StockBuyAndSellProblem {


 public static void main(String[] args) {

  //  given stock data as 
  int[] prices = {10,5,6,8,9,3};
  System.out.println(getMaxProfit(prices));
 }


 static int getMaxProfit(int[] prices) {

  if(prices.length<=1)
   return 0;

  int i = 0 ;
  int peak = prices[0];
  int valley = prices[0];
  int maxProfit = 0;
  while(i<prices.length-1) {
   while(i <prices.length-1 && prices[i]>= prices[i+1])
    i++;
   valley = prices[i];
   while(i <prices.length-1 && prices[i]<= prices[i+1])
    i++;
   peak = prices[i];

   maxProfit+=peak - valley ;

  }
  return maxProfit;
 }

}

Explanation :

 What we are doing here is as below

We are using Peak Valley Approach where are first calculate valley value in array

  • valley means lower value 
  • peak means higher value
Now while(i <prices.length-1 && prices[i]>= prices[i+1])

This is calculating the valley values, means the less value index in the array.

second, while loop is calculating the peak value in the array after this valley index.

if you see prices[i]>= prices[i+1] this means, price at current day is greater then the price at next day , that means the next day is valley or lower value, similarly for the next while as well, the price of current is less than the next day, so the next day will be peak value 

and the differences between peak and valley is actually the max profit we will earn for the day.

Time Complexity 

In this case, the time complexity will be O(n)




Hope this will help you in the interview. If you have any issue, please leave us a comment.



Thanks for reading 
Noeik

0 comments:

Post a Comment