Best Time to Buy and Sell Stock

In this problem, we are given an array in which each element represents the stock price of that day.

We have to maximize our profit by choosing a single day to buy the stock and choosing another day in the future to sell the stock. Our task is to find the maximum profit (buy price - sale price) that can obtain from these transactions and return it.

Example

To gain maximum profit we have to buy stock on 2nd day (prices = 10) and sell on 6th day (price = 90).

Note

Buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Intuition

To maximize the profit, the idea is to find the minimum element of the array and the maximum element that comes after minimum element with just one iteration of the array.

We will have one variable minPrice which will hold the minimum price value. While iterating if we find a current element value less than the minPrice, we will replace the minPrice with current element. Similarly during each pass, we will maintain a maxProfit variable that will find the difference between current element and minPrice. If the difference using current element is more than the maxProfit, we will replace the maxProfit with the new difference.

Approach

The concept is that we have to buy the stock at a minimum price and sell at a maximum price to gain maximum profit.

1. Initialize the variable minPrice and set it to INT.MAX.
2. Initialize the variable and maxProfit and set it to 0.
3. Iterate the complete array and perform the following steps 
4. minPrice = MIN( minPrice, A[i] )
5. maxProfit = MAX( maxProfit, A[i] - minPrice)
6. After the loop terminates, return maxProfit.

Complexities

• Time Complexity: O(n), where n is the size of the array
• Space Complexity: O(1)

Java Code

class BuyAndSellStock{
	
    public int getMaxProfit(int nums[]) {
        int maxProfit = 0;
        int minPrice = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            minPrice = Math.min(minPrice, nums[i]);
            maxProfit = Math.max(maxProfit, nums[i] - minPrice);
        }
        return maxProfit;
    }


    public static void main(String[] args) {

        int[] arr = new int[] { 30, 10, 40, 70, 20, 90 };

        BuyAndSellStock stocks = new BuyAndSellStock();

        int result = stocks.getMaxProfit(arr);
        System.out.println("The Maximum profit can obtain is :" + result);

    }

}

Output

The Maximum profit can obtain is :80