查找库存值数组中的买入/卖出价格以最大化正差

Question

在今天的采访中得到了这个问题,它的优化解决方案让我感到冷漠(这吹嘘,因为我真的想为这家公司工作......)

给定一组实际值,每个值代表一个公司在任意一段时间后的股票价值,找到最佳买入价格及其相应的最佳卖出价格(买入低价,卖出高价).

举一个例子来说明一下,让我们来看看Z公司的股票代码:

55.39 109.23 48.29 81.59 105.53 94.45 12.24

值得注意的是,数组在时间上是"排序"的 - 即随着时间的推移,值被附加到数组的右端.因此,我们的买入价值将(必须)在我们的卖出价值的左侧.

(在上面的例子中,理想的解决方案是买入48.29和卖出105.53)

我很容易想出O(n ²)复杂性(在java中实现)的天真解决方案:

// returns a 2-element array: first element is the index in the argument array
// of the best buying price, and the second element is the index of the best
// selling price which, collectively, maximize the trading return
//
// if there is no favorable trading (e.g. prices monotonically fall), null is returned
public int[] maximizeReturn(ArrayList<Double> prices) {
  int [] retval = new int[2];
  int BUY = 0, SELL = 1;
  retval[BUY] = retval[SELL] = -1; // indices of buy and sell prices, respectively

  for (int i = 0; i < prices.size(); i++) {
    for (int j = i + 1; j < prices.size(); j++) {
      double difference = prices.get(j).doubleValue() - 
                          prices.get(i).doubleValue();

      if (difference > 0.0) {
        if (retval[BUY] < 0 || difference > prices.get(retval[SELL]).doubleValue() - 
                                            prices.get(retval[BUY]).doubleValue()) {
          retval[BUY] = i;
          retval[SELL] = j;
        }
      }
    }
  }
  return (retval[BUY] > 0 ? retval : null);
}

这是我搞砸的地方:有一个线性时间O(n)解决方案,我完全轰炸试图解决它(是的,我知道,失败).有谁知道如何实现线性时间解决方案？(你喜欢的任何语言)谢谢!

编辑

我想,对于任何有兴趣的人,我今天刚收到的消息是,在他们问我这个问题时,我没有得到他所采访的工作.:(

Answer 1

在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);
}

编辑:新算法基于@ Joe的失败测试案例 - Nice Catch BTW!这也和@Doug T的答案一样......

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);
}

Answer 2

这是一次尝试(C++).基本上每当我追踪一个新的顶部,我试着看看这是否是最好的利润.我知道必须先发现"底部".那时我记得顶部,底部和当前的最大利润.如果稍后发现新的底部,它在当前顶部之后,那么我们必须重置顶部,看看略低的"顶部"是否可以产生更好的利润.

#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;
}

到目前为止,我已经玩了很多不同的输入集,到目前为止我没有遇到任何问题...(如果你测试这个并且看错了,请告诉我)

我强烈建议使用Austin Salonen对此问题的更新答案,并使其适应您的语言.