Problem Statement

Given an array 'stocks' in which each value at index 'i' is the stock price on day 'i', Find the maximum profit you can make by performing atmost one Buy and one Sell on these stock prices.
Example 1:
Input: [10, 1, 5, 3, 9, 4]
Output: 5
max. difference = 9-1 = 8 (you make maximum profit this way)
Example 2:
Input: [9, 5, 4, 2, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.

Solution Explanation

This is a typical trading problem where you have to buy low and sell high to make the maximum profit. The only catch here is that, you need to find the lowest value that occurs before the highest.

For example in the given Input,

      1  2  3  4  5  6
    [10, 1, 5, 3, 9, 4]

If you buy one day one and sell on day 2, you lose 9 bucks, but if you buy on day 2 and sell on day 5, you make 8 bucks and if you see that's the max you can make with given stock prices.

In the solution, as we traverse through the stock prices, we will maintain a min and maxDiff which is the current value minus the min value. The java implementaion of best time to buy and sell stock looks like below,

    public class BestTimeBuySellStockPrices {

	public static void main(String[] args) {
		int[] prices = { 10, 1, 5, 3, 9, 4 };
		System.out.println(maxProfit(prices));
	}

	public static int maxProfit(int[] prices) {
		if (prices.length <= 0)
			return 0;
		int min = Integer.MAX_VALUE, maxDiff = 0;
		for (int price : prices) {
			if (price < min) {
				min = price;
			} else {
				maxDiff = Math.max(price - min, maxDiff);
			}
		}
		return maxDiff;
	}
} 

Time Complexity

The time complexity is O(n) since we do one traversal through the stock prices.