在股票价值数组中寻找买入/卖出价格以最大化正差价

Question

在股票价值数组中寻找买入/卖出价格以最大化正差价

arraysoptimizationcomplexity-theorystocks

20

今天在面试中遇到了这个问题，它的优化解决方案让我感到崩溃（因为我真的很想在这家公司工作...）

给定一个实数数组，每个元素都代表一家公司在任意时间段后的股票价值，找出最佳购买价格及其相应的最佳售出价格（低买高卖）。

举个例子，我们来看 Company 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)的解决方案，但我完全没能想出来（是的，我知道，失败了）。有人知道如何实现这个线性时间复杂度的解决方案吗？（任何你熟悉的编程语言都可以）谢谢！

编辑

我想对于任何感兴趣的人来说，我今天刚收到消息，我没能得到那份工作，而他们就是在面试时问了我这个问题。 :(

- Magsol

1

我想看一些这方面的功能实现...这让我想起了函数式编程人员在棘手的问题上很好地处理的那种方式... - robince

你在彭博社面试过，对吧？ - Jacob Krall

干得好，不要担心工作，面试很靠运气，真的不能很好地衡量现实世界的表现。 - Brian Ogden

24个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Edward Vakhovsky · Answer 1

这是一个可行的C语言解决方案：

void bestBuySell() { double prices[] = {10.50, 10.0, 3.0, 194.0, 55.39, 2.0, 109.23, 48.29, 81.59, 105.53, 94.45, 191.0, 200.0, 12.24}; int arrSize = 14; double bestBuy = prices[0], bestSell = prices[1], bestPotentialBuy = prices[0]; double potentialProfit = prices[1] - prices[0];

for(int i = 1; i < (arrSize-1); i++)
{
    if(prices[i] < bestBuy)
        bestPotentialBuy = prices[i];            

    if((prices[i+1] - bestPotentialBuy) > potentialProfit)
    {
        bestBuy = bestPotentialBuy;
        bestSell = prices[i+1];
        potentialProfit = prices[i+1] - bestPotentialBuy;
    }
}

printf( "bestBuy %f bestSell %f\n", bestBuy, bestSell );

}

- Eric Tsai · Answer 2

另一个 Ruby 解决方案：

# Here's some examples. Please feel free to give your new test.
values = [55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24]
# values = [5, 6, 4, 7, 9, 8, 8]
# values = [5, 10, 4, 6, 7]
# values = [5, 10, 4, 6, 12]
# values = [1, 2, 3, 4, 5]



# Initialize parameters.
min = values[0]
best_buy_time = values[0]
best_sell_time = values[0]
max_profit = 0



# This solution is based on comparing previous k elements and k+1 one.
# The runtime is O(n) and it only use O(1) auxiliary storage.
values.each_with_index do |value, index = 1|

  # Check value in this turn.
  puts value

  # Check current value is bigger than min or not.
  # If not, we find the new min.
  if value <= min
    min = value

  # If current value is bigger than min and
  # (value - min) is bigger than previous max_profit,
  # set new best_buy_time, best_sell_time & max_profit.
  else
    if value - min >= max_profit
      best_buy_time = min
      best_sell_time = value
      max_profit = value - min
    end

  end

end



# Let's see about the result.
puts "\nbest_buy_time: ", best_buy_time, "\nbest_sell_time: ", best_sell_time, "\nmax_profit: ", max_profit

- Shaheen Ghiassy · Answer 3

这是我使用Javascript的尝试。该脚本以O（N）计算答案：

//Main Stock Array
var stock = [15, 20, 0, 3, 30, 45, 67, 92, 1, 4, 99];


//Setup initial variable state
var ans = {}, tmp = {}; //These are just for namespacing / syntatic sugar
ans.minVal = stock[0];
ans.minInd = 0;
ans.maxDiff = stock[1] - stock[0];
ans.maxInd = 1;
tmp.minInd = ans.minInd;
tmp.minVal = ans.minVal;

//Basically we iterate throught the array. If we find a new low, we start tracking it. Otherwise we compare the current index against the previously found low
for(i = 1; i <= stock.length-1; i++) {
    if(tmp.minVal > stock[i]) {
        tmp.minVal = stock[i];
        tmp.minInd = i;
    } else {
        ans.diff = stock[i] - stock[tmp.minInd];
        if(ans.diff > ans.maxDiff) { //Looks like we found a new maxDifference. Lets log the indexes
            ans.maxDiff = ans.diff;
            ans.maxInd = i;
            ans.minInd = tmp.minInd;
            ans.minVal = tmp.minVal;
        }
    }
}

document.write('You should buy your stocks on day ' + ans.minInd + ' and sell on day ' + ans.maxInd);

- Dmitry Sevastianov · Answer 4

对于那些对函数式编程感兴趣的人来说，这是一个 F# 解决方案。尽管我不会说它有太大的不同。

let start, _, profit = 
    [55.39; 109.23; 48.29; 81.59; 81.58; 105.53; 94.45; 12.24 ]
    |> Seq.fold (fun (start,newStart,profit) i -> 
                    let start = defaultArg start i
                    let newStart = defaultArg newStart i
                    let newProfit = i - newStart
                    if profit < newProfit 
                    then  Some newStart, Some newStart,newProfit
                    else if start > i 
                    then Some start, Some i, profit 
                    else Some start,Some newStart,profit) (None,None, 0.0)
printf "Best buy: %f; Best sell: %f" start.Value (start.Value + profit)

输出：

Best buy: 48.290000; Best sell: 105.530000