This is maximum sub-array problem. Nice explaination is given in CLRS -
"Introduction to algorithms " Pg 68, ch-4 3rd edition
On Tue, Aug 7, 2012 at 11:00 AM, Navin Gupta <navin.nit...@gmail.com> wrote:
> @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.
>
--
With Regards
Manish Patel
BTech Final year
Computer Science And Engineering
National Institute of Technology -Allahabad
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
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.
