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