This is a linear time constant space algorithm.
Assume the stocks prices are given in an array where index represents the
day no . For ex a[365] represents stock price on 365th day of year.
Find the min and max element in the array.
If the min comes before max, then return the dates- min to buy and max to
sell.
But if the min comes after max,
find the max element that comes after min i.e. maxRight
& find the min element that comes before max i.e. minLeft
Now find the difference (max - minLeft) & ( maxRight - min)
return the dates for which the difference is higher.
Code:--
void FindDaytoBuySellStock(int stocks[], int N) // here N = 365
{
int minPos = findMinPos(stocks);
int maxPos = findMaxPos(stocks);
if(minPos < maxPos ) { BuyDate = minPos,SellDate = maxPos; }
else{
minLeft = find min in array from 0 to maxPos-1
maxRight = find max in array from minPos+1 to N
int d1 = max - minLeft;
int d2 = maxRight - min;
if(d1 <= d2 ) { BuyDate = minLeft,SellDate = max; }
else{ BuyDate = min ,SellDate = maxRight; }
}
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/dSJCOIuUuKUJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
