This can be done in O(n) time complexity and O(1) space complexity using
dynamic programming.Consider a situation in which I have been given an
array of stock values for N days (in your case N=365) which looks like:
int a [ ] = { 5, 10, 4, 6, 7 };
Now,use two variables min (which will keep track of minimum element found
upto some index i) and max_profit (keeps track of maximum profit that can
be obtained ).
int min = a[0]; // initialized to first element
int max_profit = 0; //when you buy and sell on same day
for ( int i = 1; i < n; i++ ){
if ( max_profit < (a[i] - min ) )
max_profit = a[i] - min;
if ( a[i] < min )
min = a[i];
}
Finally. I'll have min and max_profit, so if you need to find the buying
and selling day you can easily calculate using min and max_profit.
Buying day = min;
Selling day = min+max_profit;
I hope it's clear.Even if something is wrong or difficult to understand you
can check this link :
http://stackoverflow.com/questions/7086464/interview-question-maximum-single-sell-profit
Thanks.
On Sun, Aug 5, 2012 at 10:07 AM, harsha <harshacoo...@gmail.com> wrote:
> there is a stock company whose stock prices are known to u for next 365
> days. u have to write the code on which day u should buy and sell the
> stock. U cannot sell a stock until you haven't bought any stock.
>
> my approach was to buy the stock when the stock prices are the lowest and
> sell them when they are the highest. But i think am missing something
> because this question was for a considerable amount of marks but the
> solution is too obvious! any thoughts ?
>
> --
> 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/-/Qw0NRAP_TtwJ.
> 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.
>
--
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.
