Wednesday 28 August 2013

Find the Best Time To Buy And Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to buy one share of the stock and sell one share of the
stock, design an algorithm to find the best times to buy and sell.

Ex:
Input = {6,1,3,2,4,7}
Output : time to buy = at index 1(value = 1)
             time to sell  = at index 5(value = 7)
             max profit   = 7 - 1 = 6

class BestTimeToBuyAndSellStock{
static void find(int []a){
//Boundary Condition
if(a == null || a.length == 0)
return;

int buy = -1, sell = -1, max = Integer.MIN_VALUE;
int min = 0, diff;
 
  for(int i = 1; i < a.length; i++){
if(a[i] < a[min])
min = i;

diff = a[i] - a[min];
if(diff > max){
max = diff;
buy = min;
sell = i;
}
}
System.out.println("buy "+buy+"\nSell "+sell+"\nMax "+max);
}

public static void main(String... args){
int []array = {6,1,3,2,4,7};
find(array);
}
  }

Time Complexity : O(N)
Space Complexity : (1) 

No comments:

Post a Comment