Найти цены покупки / продажи в массиве стоимости акций, чтобы максимизировать положительную разницу

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) , и я полностью бомбил, пытаясь выяснить это (да, я знаю, FAIL). Кто-нибудь знает, как реализовать решение с линейным временем? (любой язык, с которым вам удобно) Спасибо!

Редактировать

Полагаю, для тех, кто заинтересован, я только что получил сегодня сообщение, что не получил работу, на которую я брал интервью, когда мне задавали этот вопрос. (

Answer 1

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

Answer 2

Решение в скале:

Пример: [7, 2, 5, 6, 1, 3, 6, 4]

Сохраните указатель на последнюю минимальную цену акций (lastStockPrice) и сравните ее с текущей ценой акций. Когда вы достигаете точки, где текущая цена акции <последняя минимальная цена акции, вы обновляете lastStockPrice. </p>

При циклическом просмотре массива отслеживайте максимальную разницу (прибыль) между currentPrice и lastStockPrice, поскольку прибыль может измениться при обновлении lastStockPrice.

Приведенный ниже scala-код работает за O (n) времени и занимает постоянное количество места.

object Solution {
    def maxProfit(prices: Array[Int]): Int = {
        var lastStockPrice = Int.MaxValue
        var maxProfit = 0
        for(currentPrice <- prices){
            if(currentPrice < lastStockPrice){
                lastStockPrice = currentPrice;
            }else if(currentPrice - lastStockPrice > maxProfit){
                maxProfit = currentPrice - lastStockPrice;
            }
        }
        maxProfit
    }
}

Answer 3

Я хотел бы описать, как я подошел к этой проблеме, чтобы облегчить понимание моего кода:

(1) Если бы в этот день мне приходилось продавать свои акции, какую минимальную сумму я мог бы заплатить, чтобы купить их? По сути, я отслеживаю минимальную цену до этого дня

(2) За каждый день, если я буду продавать в этот день, сколько я буду зарабатывать? (Цена акций в этот день - минимальная цена)

Это показывает, что я должен отслеживать две вещи: (1) минимальная цена акций на данный момент (2) лучший доход на данный момент.

Проблема заключается в выборе дня для продажи. Я продам в тот день, который даст мне лучший заработок. Вот мой код Java:

    public static void findBestDeal(double [] stocks) {
    double minsofar = stocks[0];
    double bestsofar = 0.0;

    for(int i=1; i< stocks.length; i++) {

        // What is the cheapest price to buy it if I'm going to sell it today
        if(stocks[i-1] < minsofar) {
            minsofar = stocks[i-1];
        }

        // How much do I earn if I sell it on ith day?
        double current_deal = stocks[i] - minsofar;

        // Is selling today better?
        if(current_deal > bestsofar) {
            bestsofar = current_deal;
        }
    }

    System.out.println("Found the best deal: " + bestsofar + " (Bought at " + minsofar + " and sold at " + (minsofar+bestsofar) + ")");

}