Question: Let us suppose we have an array whose ith element gives the price of a share on the 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.
When we talk about the best times to sell and buy, we mean that we want the best profit possible. A profit is possible when our buying rate is less than the selling rate. We need to maximize this profit, to be better than others.
At first glance, we might think that finding the minimum and maximum value would do, but it does have a hidden restriction, that is: You must buy before you can sell.
So we can say that the question is equivalent to:-
Find i and j that maximizes Aj – Ai, where i < j.
We can obviously solve it in O(n2), by finding all the possible permutations and then determining the maximum profit. But, let us try to understand an O(n) approach.
– To solve this problem efficiently, we would need to track the minimum value’s index.
– As we traverse, update the minimum value’s index when a new minimum is met.
– Then, compare the difference of the current element with the minimum value.
– Save the buy and sell time when the difference exceeds our maximum difference (also update the maximum difference).
Here is an implementation of the above algorithm-
#include<stdio.h> void getBestTime(int stocks[], int size) { int buy = 0, sell = 0; int min = 0; int i; int maxDiff = 0; buy = sell = 0; for (i = 0; i < size; i++) { if (stocks[i] < stocks[min]) min = i; int diff = stocks[i] - stocks[min]; if (diff > maxDiff) { buy = min; sell = i; maxDiff = diff; } } printf("\nThe day to buy is- %d at price %d",buy, stocks[buy]); printf("\nThe day to sell is- %d at price %d",sell, stocks[sell]); } int main(void) { int stocks[] = {3, 6, 10, 2, 66, 43, 1, 23}; int buy = 0; int sell = 0; getBestTime(stocks, 8); return 0; }
Here is the running link for the code:- http://ideone.com/AqZBMq
3 comments
I had that question on an interview in broadcom, I wrote this code and it worked great. Thanks.
It has a nother question, if you get the array and the amount of money lets say 1000$ where can you get the best profit.
[3 5 1 2] the biggest profit would be (1,2) I ern 1000$
When in (3,5) only 660$
,but the solution is pretty easy if you know the first question.
I don’t think this works at all. It doesn’t enforce the role of having to sell after you buy and even if you did by resetting the sell pointer when resetting the min, it would fall into a local minimum (eg picking 1 and 23 in your example instead of 2 and 66 like it should).
I would make two arrays. 1 traversing from the left and keeping track of the min price up to that point and another traversing right to left keeping track of the max up to that point. Taking the max differences of the two arrays will give you the min and max that yield the highest difference.
If only the real stock market just have you an array.
Hi Kevin,
Can you point out a sample input case where this solution fails. I will be happy to correct the solution.
Thanks.
Comments are closed.