Find buy/sell prices in array of stock values to maximize positive difference
In C#:
static void Main(string[] args){ double[] values = new double[7]{55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24}; double max = double.MinValue, maxDiff = double.MinValue, diff = 0; for (int i = 1; i < values.Length; i++) { if (values[i] > values[i - 1]) { //trending upward, append to existing differential diff += values[i] - values[i - 1]; } else { //trending downward, reset the diff diff = 0; } if (diff > maxDiff) { maxDiff = diff; max = values[i]; } } Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);}EDIT: New algo based on @Joe's failing test case -- Nice Catch BTW! It's also the same answer as @Doug T's now...
static void Main(string[] args){ double[] values = new double[8] { 55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24 }; double max = double.MinValue, maxDiff = double.MinValue, diff = 0; double bottom = values[0]; for (int i = 1; i < values.Length; i++) { diff += values[i] - values[i - 1]; if (diff > maxDiff) { maxDiff = diff; max = values[i]; } if (values[i] < bottom) { bottom = values[i]; diff = 0; } } Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);}
Here's an attempt (C++). Basically everytime I track a new top, I try to see if thats the best profit thusfar. I know that the "bottom" must have been discovered earlier. At that point I remember the top, bottom, and the current max profit. If a new bottom is discovered later, its AFTER the current top, so we must reset top and see if a slightly lower "top" can yield better profit.
#include <iostream>int main(){ double REALLY_BIG_NO = 1e99; double bottom = REALLY_BIG_NO; // arbirtrary large number double currBestBuy = 0.0; double top = 0.0; double currBestSell = 0.0; double profit = 0.0; // array of prices double prices[] = {10.50, 55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24, 152.0, 2, 170.0}; int numPrices = 10;// number of prices for (int i = 0; i < numPrices; ++i) { if (prices[i] < bottom) { bottom = prices[i]; // reset the search on a new bottom top = 0.0; } else if (prices[i] > top) { top = prices[i]; // calculate profit double potentialProfit = (top - bottom); if (potentialProfit > profit && bottom != REALLY_BIG_NO) { profit = potentialProfit; currBestSell = top; currBestBuy = bottom; } } } std::cout << "Best Buy: " << currBestBuy << "Best Sell: " << currBestSell << std::endl;}So far I've played around with a bunch of different input sets, and so far I haven't had any problems... (let me know if you test this and see anything wrong)
I highly recommend using Austin Salonen's updated answer to this question and adapting it to your language.
The idea is simple. Keep two pointers, lo and hi.
Do a Foor loop
- if price is higher than hi, update hi = price, continue
- if the price is lower than hi. Then lo and hi is one of possible candidates. Calculate the profit, store it if it's bigger than previous profits and reset lo, hi to price
def getBestProfit(prices): lo = hi = profit = 0 for price in prices: if lo == 0 and hi == 0: lo = hi = price if price > hi: hi = price if price < low: tmpProfit = hi - lo if tmpProfit > profit: profit = tmpProfit lo = hi = price return profitThat's it