Given an array of numbers which indicates the prices of stocks for a period of time. We have to find the two values in the array such that their difference is maximum and also the greater value must appear later than smaller value.
In another way, we have to find the buying and selling price of the stock so that we get maximum profit.
For example for the following array we can make a profit of 6 if you buy the stock @ 1 and sell it @ 7
[4, 8, 1, 5, 7, 6]
We can always find the correct solution if we try to examine each possible pair. This method is based on my previous post. It runs in O(n2) time.
But we want to design a linear time solution (i.e. O(n) ) and constant space (O(1)).
Here is how our algorithm works. We start from the end of the array and keep track of the maximum value encountered so far. We also find the difference between the current element and the maximum element. If the difference is greater than previous difference, we will update it.
Here is the Java implementation of the above solution. This approach takes O(n) time and iterate through the array only once. We assume that the array contains at least two elements. This program returns 0 if the stock prices in decreasing order.
/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 10/1/13
* Time: 12:01 AM
* To change this template use File | Settings | File Templates.
*/
public class Main {
public static void main(String[] args)
{
//int[] stockPrice = {3,1,2,6,8,7,9,4,5};
//int[] stockPrice = {2, 3, 10, 6, 4, 8, 1};
int[] stockPrice = { 7, 5, 4, 6, 3, 2};
System.out.println( getMaxProfit(stockPrice) );
}
//Returns the max profit you can make for the given stock prices
//Assumes that there are at least 2 entries
public static int getMaxProfit(int[] price)
{
int maxProfit = 0;
//Init the max price with last item
int maxPrice = price[price.length-1];
for( int i = price.length - 2; i >= 0; --i )
{
int profit = maxPrice - price[i];
//update the maximum profit
if( profit > maxProfit )
maxProfit = profit;
//update the maximum price
if( price[i] > maxPrice )
maxPrice = price[i];
}
return maxProfit;
}
}