Buy and sell stocks | Part 1

Algorithm/Insights

For the stock price array - {100, 80, 120, 130, 70, 60, 100, 125}, maximum profit obtainable at the end of each day is shown below.

If you observe above chart carefully, you should be able to notice that: for any given day, maximum profit obtainable is maximum of 1.Maximum profit obtained till previous day,  2.Stock price on that day - minimum stock price so far.

Therefore, to find out the maximum profit obtainable for a given window, all we need to is to keep track of minimum stock price seen so far (starting from day-1) and maximum profit obtained so far. Maximum profit obtained so far can be computed using above observation. Maximum profit obtained so far is initialized to 0 and minimum stock price seen so far is initialized to MAX_VALUE.

Please checkout function maximumProfit(int[] stockPrices) in code snippet for implementation details.

Please add comments in case you have any queries/feedback.

Code Snippet

			
package com.ideserve.virendra.questions;

public class BuyAndSellStocks 
{
    public static int maximumProfit(int[] stockPrices)
    {
        int profit = 0;
        int minimumPrice = Integer.MAX_VALUE;
        /* 
         * for any given day, maximum profit obtainable is - 
         * maximum of(maximum profit obtained till previous day, stock price on that day - minimum stock price so far)
         */
        for(int i = 0; i < stockPrices.length; i++)
        {
            profit = Math.max(profit, stockPrices[i] - minimumPrice);
            minimumPrice = Math.min(stockPrices[i], minimumPrice);
        }
        
        return profit;
    }

    public static void main(String args[])
    {
        int[] stockPrices = {100, 80, 120, 130, 70, 60, 100, 125};
        
        System.out.println("maximum profit that could be obtained is: " + maximumProfit(stockPrices));
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)