Heres a pretty simple but interesting problem to solve.  Also a popular interview question!

Problem

Given a list of stock prices for a specific stock over time in chronological order, figure out what is the maximum profit that could have been made by making exactly one buy and one sell of this stock. Return 0 if it is not possible to make a profit.

For example, given the stock prices $10, 9, 8, 7, 5$, it is not possible to make a profit so it should return 0. Given the stock prices $13, 3, 12, 1, 11$, the maximum profit that can be made is 10 (by buying at 1 and selling at 11).

Algorithm

The optimal algorithm is actually fairly simple. Here it is coded in java:

public static double maxProfit(double[] prices) {
if (prices.length <= 0) {
return 0;
}

double lowSoFar = prices[0];
double maxProfitSoFar = 0.0;
for (int i = 1; i < prices.length; i++) {
// Keep track of the lowest price so far.
if (lowSoFar > prices[i]) {
lowSoFar = prices[i];
}

// This is the maximum profit possible if we sell at i.
double profit = prices[i] - lowSoFar;

if (profit > maxProfitSoFar) {
maxProfitSoFar = profit;
}
}

return maxProfitSoFar;
}


The idea here is that as we loop through the array we keep track of the lowest value so far. If we subtract the lowest value so far from the current value we are at in the array, we find the maximum profit that can be made by selling at the current point in the array. Since we are calculating that value for every ending point, the maximum of all those values will be our solution!

Since we just need to loop through the prices array once, the time complexity is $O(n)$ (where $n$ is the size of the $prices$ array).

Be Sociable, Share!