The Stock Market Problem

Question: Let us suppose we have an array whose i^th 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(n²), 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