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

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

Вот решение для JavaScript ..

function getMax(arr){
        //we need more than at least 3 ints to be able to do this
        if(arr.length <= 1) return arr;
        // get the minimum price we can sell at to make a profit
        var min = arr[0];
        //get the first potential maximum profit
        var max = arr[1] - arr[0];

        //while looping through we must get a potential value, 
       //we can then compare that using the math.max using the maximum
      //and the potential prices that we have seen. Once the loop runs the ouput here should be 6!
        for(var i = 1; i < arr.length; ++i){
            var current = arr[i];
            var potential = current - min;

            max = Math.max(max, potential);
            min = Math.min(min, current);
        }

        return max;
    }

    console.log(getMax([10, 7, 5, 8, 11, 9]));

Время выполнения для этого O (n)

Answer 2

Я действительно должен указать на вопрос собеседования, который ожидает, что вы решите его, поскольку O (n) является пограничным абсурдом. Интервью вопросы предназначены, чтобы доказать, что вы можете решить проблему, которую вы смогли решить. Тот факт, что вы решили это в O (N ^ 2) против O (N), не имеет значения. Если бы компания перестала нанимать вас за то, что вы не решили эту проблему в O (N), это, вероятно, не та компания, в которой вы бы хотели работать.

Answer 3

Я придумал следующий алгоритм для этой проблемы, похоже, работает для всех входов. Кроме того, если стоимость акции продолжает падать, программа выдаст сообщение о том, что не следует покупать эту акцию:

  public class GetMaxProfit 
  { 

  double minValue = -1, maxValue = -1;
  double maxDiff = 0;

  public void getProfit(double [] inputArray){
    int i=0, j=1;
    double newDiff = 0;
    while(j<inputArray.length){
         newDiff = inputArray[j]-inputArray[i];
         if(newDiff > 0){
             if(newDiff > this.maxDiff){
               this.minValue = inputArray[i];
               this.maxValue = inputArray[j];
               this.maxDiff = newDiff;
             }
        }
        else{
            i = j;
        }
        j++;
    }
 }

 public static void main(String[] args) {
    // TODO Auto-generated method stub
    GetMaxProfit obj = new GetMaxProfit();

    obj.getProfit(new double[]{55.39, 19.23, 14.29, 11.59, 10.53, 9.45, 1.24});
    if(obj.minValue != -1 && obj.maxValue != -1){
      System.out.println("Buy Value for the input: "+obj.minValue);
      System.out.println("Sell Value for the input: "+obj.maxValue);
      System.out.println("Best profit for the input: "+obj.maxDiff);
            }
            else
               System.out.println("Do Not Buy This STOCK!!);

 }

}

Есть ли здесь какой-то улов? Время сложность O (N)

Answer 4

1.Мы не можем просто взять наименьшую сумму среди значений в качестве «Best Buy» и максимальную сумму в качестве «Best Sell», потому что «Sell» должно произойти после «Buy».

2. Мы не должны рассматривать зарегистрированный минимум как «Лучшая покупка», поскольку в последующие дни могут иметься акции, разница которых с зарегистрированным минимумом может привести к прибыли, которая может быть меньше, чем «зарегистрированная прибыль».

3.Best Buy и Best Sell рассматриваются как один вариант, потому что именно положительная разница между этими значениями дает максимальную прибыль.

4. Так как любой зарегистрированный минимум в прошлом является потенциальным кандидатом на покупку, условие максимальной прибыли всегда должно быть проверено по зарегистрированному минимуму и цене акций текущего дня. Поэтому мы всегда должны отслеживать записанный минимум, но просто наличие зарегистрированного минимума не составляет «Best Buy» из-за причины № 2.

Теперь будет иметь смысл следующий код, который выполняется за O (n) раз.

public class BestStockBuyAndSell {

public static void main(String[] args) {

    double[] stockPrices = {55.39,109.23,48.29,81.59,105.53,94.45,12.24};
    int [] bestBuySellIndex = maxProfit(stockPrices);

    System.out.println("Best Buy At "+stockPrices[bestBuySellIndex[0]]);
    System.out.println("Best Sell At "+stockPrices[bestBuySellIndex[1]]);

    System.out.println("Max Profit = "+(stockPrices[bestBuySellIndex[1]]-stockPrices[bestBuySellIndex[0]]));

}

public static int[] maxProfit(double[] stockPrices)
{
    int bestBuy=0;
    int bestSell=0;

    int[] bestCombination ={bestBuy,bestSell};
    double recordedMinimum = stockPrices[bestBuy];
    int recordedMinimuIndex = bestBuy;
    double bestProfitSofar = stockPrices[bestSell] - stockPrices[bestBuy];

    for(int i=1;i<stockPrices.length;i++)
    {
        if(stockPrices[i] - recordedMinimum > bestProfitSofar)
        {

            bestProfitSofar = stockPrices[i] - recordedMinimum;
            bestSell = i;
            bestBuy = recordedMinimuIndex;
        }

        if(stockPrices[i] < recordedMinimum)
        {
            recordedMinimuIndex = i;
            recordedMinimum = stockPrices[i];
        }

    }

    bestCombination[0] = bestBuy;
    bestCombination[1] = bestSell;


    return bestCombination;

}

}

Answer 5

Это решение C, которое действительно работает:

void bestBuySell () { двойные цены [] = {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 = цены [0], bestSell = цены [1], bestPotentialBuy = цены [0]; double потенциалаProfit = цены [1] - цены [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 );

}

Answer 6

Вот моя попытка использования 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);

Answer 7

В моих попытках выучить го, а также разбить мне мозг на этом, вот моя попытка.

func GetMaxProfit2(prices []float64) (float64, float64) {
    var min, max, pmin, pmax int

    for i, v := range prices {
        if v - prices[min] > prices[max] - prices[min] {
            pmax = max
            max = i
        }
        // Reset the max when min is updated.
        if v < prices[min] {
            pmin = min
            min = i
            pmax = max
            max = i
        }
    }

    // If min is ahead of max, reset the values back    
    if min >= max {
        min = pmin
        max = pmax
    }

    return prices[min], prices[max]
}

Answer 8

что по этому поводу?

min = 100000000
max = 0

for elem in inp:
    if elem < min:
       min = elem
    tempMax = elem-min
    if tempMax > max:
        max = tempMax

print(max)

Answer 9

Вот мое решение, такое же, как у @Doug T. Но я также отслеживаю день в индексе. Пожалуйста, оставьте отзыв.

 int prices[] = {4,4,5,6,2,5,1,1};
 //int prices[] = {100, 180, 260, 310, 40, 535, 695};

 int currentBestSellPrice=0;
 int currentBestBuyPrice=0;
 int lowindex=0;
 int highindex=0;
 int low=prices[0];
 int high=prices[0];
 int profit=0;
 int templowindex=0;
 for(int i=0; i< prices.length;i++)
 {
     // buy low
     if(prices[i] < low && i+1 < prices.length)
     {
         low = prices[i];  
         templowindex=i;
         high=0;
     }
     // sell high
     else if(prices[i] > high)
     {
         high = prices[i];
         int potentialprofit = (high-low);
         if(potentialprofit > profit)
         {
             profit = potentialprofit;
             currentBestSellPrice = high;
             currentBestBuyPrice = low;
             highindex=i;
             lowindex=templowindex;
         }
     }
 }


 System.out.println("Best Buy Price : "+ currentBestBuyPrice + " on day "+ lowindex);
 System.out.println("Best Sell Price : "+ currentBestSellPrice+ " on day "+ highindex );

Answer 10

Решение в javascript

var stockArr = [13931, 9889, 987, 4, 89, 100];

function getBestTime(sortedArr) {
  var min = 0;
  var buyIndx = 0;
  var saleIndx = 0;
  var maxDiff = 0;
  for (var i = 0; i < stockArr.length; i++) {
    if (stockArr[i] < stockArr[min]) {
      min = i;
    }
    var diff = stockArr[i] - stockArr[min];
    if (diff > maxDiff) {
      buy = min;
      sale = i;
      maxDiff = diff;
    }
  }
  return {
    buy:buy+1,
    sale:sale+1,
    diff:maxDiff
  }
}

console.log(getBestTime(stockArr));