© Parineeth M R

** 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^{2}) 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