Maximum profit given stock prices – The Coding Interview Blog

Question 52. Given a set of stock prices over a period of time, find the maximum profit possible by buying and selling the stocks. For instance, if the stock prices are 100, 90, 200, 20, 70, 150, 10 and 40, then the maximum profit = 150 – 20 = 130

If we use a brute force approach, then we will compare every pair of numbers to find the maximum profit possible. This requires O(n²) operations. However using the greedy approach we can solve the problem in O(n). The main idea of the greedy approach is that it is sufficient to maintain the minimum stock price that we have encountered so far as we traverse the stock prices.

The procedure is as follows: as we traverse the stock price list, subtract the minimum stock price seen so far from the current stock price to figure out the profit. If the profit is greater than the maximum profit so far, then update the maximum profit.

The working of the algorithm on the stock prices {100, 90, 200, 20, 70, 150, 10, 40} is given below. The minimum stock price is initialized to the first element 100. The max profit is initialized to 0. We start from the second stock price onwards.

C/C++


/*
stock_price: array of stock price values
n: number of elements in the array
Return value: maximum profit possible
*/
int find_max_profit(int stock_price[], int n)
{
	int i, min_stock_price, cur_profit, max_profit;

	max_profit = 0;
	if (n <= 1)
		return max_profit;

	min_stock_price = stock_price[0];

	for (i = 1; i < n; ++i) {
		
		cur_profit = stock_price[i] - min_stock_price;

		if (cur_profit > max_profit)
			max_profit = cur_profit;

		if (stock_price[i] < min_stock_price)
			min_stock_price = stock_price[i];
	}

	return max_profit;
}

Java


/*
stockPrice: array of stock price values
Return value: maximum profit possible
*/
public static int findMaxProfit(int[] stockPrice) {
	int n = stockPrice.length;

	int maxProfit = 0;
	if (n <= 1)
		return maxProfit;

	int minStockPrice = stockPrice[0];

	for (int i = 1; i < n; ++i) {
	
		int curProfit = stockPrice[i] - minStockPrice;

		if (curProfit > maxProfit)
			maxProfit = curProfit;

		if (stockPrice[i] < minStockPrice)
			minStockPrice = stockPrice[i];
	}

	return maxProfit;
}

Python


#stock_price: list of stock price values
#Return value: maximum profit possible
def find_max_profit(stock_price) :
	n = len(stock_price)

	max_profit = 0
	if (n <= 1):
		return max_profit

	min_stock_price = stock_price[0]

	for  i in range(1, n):
		cur_profit = stock_price[i] - min_stock_price

		if (cur_profit > max_profit):
			max_profit = cur_profit

		if (stock_price[i] < min_stock_price):
			min_stock_price = stock_price[i]
	
	return max_profit