Given an array of stock prices, where the increasing indexes of the array signify the increase in time. Return a good time to buy and sell such that profit is maximized.

Suppose we are given an array of n integers representing stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit.

For example, price = [23171, 21015, 21123, 21366, 21013, 21367] then maximum single sell profit will be price[5] – price[4] = 21367 – 21013 = 354.

We can solve it by some modification to Kadane’s Algorithm described here in my previous post.

Kadane’s Algorithm
Basically we keep keep track of minimum price so far to buy and maximum price so far so that profit (buy-sell) is maximized ate that point. Below is a simple implementation of this approach i O(n) time and o(1) space.

public static int maxStockProfit(int[] price)
{
	int maxProfit = 0;
	int minBuy = price[0];
	int tempStart = 0;
	int start = 0;
	int end = 0;
	
	for(int i=1; i<price.length;i++)
	{
		if(price[i] < minBuy)
		{
			minBuy = price[i];
			tempStart = i;
		}
		if((price[i] - minBuy) > maxProfit)
		{
			maxProfit = price[i] - minBuy;
			start = tempStart;
			end = i;
		}
	}
        return maxProfit;
}