@ashgoel :- Thanx for pointing it out, my earlier approach doesn't work.
Please check if this works.
We can apply this:-
For every element, find the highest element to the right of it.
For e.g:
I/P:- 35 40 15 35 10 20
Highest to Right:- 40 35 35 20 20 -
Now at every point, we will find the difference of both and keep track of
the buy and sell dates.
This can be done in linear time without any space.
void getDates( int price[] ) {
int maxSel l, maxBuy , maxGain= INT_MIN;
int Sell,Buy,curGain;
Sell = n;
for(int i=n-1;i>=0;i--)
{
curGain = price[Sell] - price[i];
if(curGain > maxGain){ // buying today gives more gain
that previous gain found, update the maxgain and buy,sell dates
maxGain = curGain;
maxBuy = i; // today
maxSell = Sell;
}
if( price[i] > price[Sell] ) // here selldate is
updated
Sell = i ;
}
}
--
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/-/BrQFNo1PKTIJ.
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.
