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

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

В 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's сейчас ...

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

До сих пор я играл с кучей различных входных наборов, и до сих пор у меня не было никаких проблем ... (дайте мне знать, если вы проверите это и увидите что-то не так)

Я настоятельно рекомендую использовать обновленный ответ Остина Салонена на этот вопрос и адаптировать его к вашему языку.

Answer 3

Идея проста. Держите два указателя, вот и привет.
Сделай цикл Foor

1. если цена выше чем hi, обновить hi = price, продолжить
2. если цена ниже чем привет. Тогда вот и привет - один из возможных кандидатов. Рассчитайте прибыль, сохраните ее, если она больше предыдущей прибыли, и сбросьте ее, привет в цену

def getBestProfit(prices):
    lo = hi = profit = 0</p>

<code>    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 profit
</code>

Вот и все

Answer 4

void getBestTime (int stocks[], int sz, int &buy, int &sell){
int min = 0;
int maxDiff = 0;
buy = sell = 0;
for (int i = 0; i < sz; i++) 
{
    if (stocks[i] < stocks[min])
    {
        min = i;
    }
    int diff = stocks[i] - stocks[min];
    if (diff > maxDiff) 
    {
        buy = min;
        sell = i;
        maxDiff = diff;
    }
}}

На всякий случай, если вы предпочитаете этот ответ. Я нашел это в другой сети, но все же. источник: http://leetcode.com/2010/11/best-time-to-buy-and-sell-stock.html

Answer 5

      public void profit(float stock[], int arlen ){
            float buy = stock[0];
            float sell = stock[arlen-1];
            int bi = 0;
            int si = arlen - 1;

            for( int i = 0; i < arlen && bi < si ; i++){

                    if( stock[i] <  buy && i < si){
                            buy = stock[i];
                            bi = i;
                    }
                    if(stock[arlen - i - 1] > sell &&  (arlen - i -1)  > bi){
                            sell = stock[arlen - i - 1];
                            si = arlen - i - 1;
                    }
            }
            System.out.println(buy+" "+sell);
    }

Answer 6

Другое решение 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

Answer 7

Я думал об этом так: для каждого индекса i каким будет идеальный индекс для продажи этой акции? Это, конечно, индекс максимального значения после i. Это сводит нашу проблему к поиску максимального элемента после индекса i для каждого i в [1 ... n] Если бы мы могли сделать это за O(n) время, то мы могли бы найти лучший выбор среди них и сообщить об этом.

Один из способов сделать это - начать обход с конца массива, поддерживая две переменные: одну, чтобы сохранить самый большой элемент, который мы встречали до сих пор max_till_now, и одну, чтобы сохранить максимальную прибыль, которую мы могли получить до сих пор profit. Это просто так, что мы можем сделать это за один проход. Мы также могли бы использовать дополнительное пространство и для каждого элемента i сохранить для него индекс самого большого элемента в диапазоне [i + 1 ... n], а затем найти максимальную прибыль.

Вот мой код Python:

def buyLowSellHigh(L):
    length = len(L)
    profit = 0
    max_till_now = L[length - 1]
    for i in xrange(length - 2, -1, -1):
        if L[i] > max_till_now: max_till_now = L[i]
        else:
            if max_till_now - L[i] > profit: profit = max_till_now - L[i]
    return profit

Answer 8

Я получил 100% за то же самое, вот, пожалуйста.

public int solution(int[] A) {
      if (A == null || A.length<=1){
            return 0;
        }
        int minValue = Math.min(A[0], A[1]);
        int profit = A[1] - A[0];
        for (int i = 2; i < A.length; i++) {
          minValue = Math.min(minValue, A[i]);
          profit = Math.max(A[i] - minValue,profit);
        }

        return profit > 0 ? profit : 0;
}

Answer 9

Вот мое решение в Ruby:

values = [55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24]

max_diff = 0
diff = 0
min = values[0]
max = 0

values.each_with_index do |value, index = 1|
  # get an array of the previous values before the current one
  lag_values = values[0..index]

  # get the minimum of those previous values
  min_lag_value = lag_values.min

  # difference between current value and minimum of previous ones
  diff = values[index].to_i - min_lag_value.to_i

  # if current difference is > previous max difference, then set new values for min, max_diff, and max
  if diff > max_diff
    max_diff = diff
    min = min_lag_value
    max = values[index]
  end
end

min # => 48.29
max # => 105.3
max_diff # => 57

Приветствия

Answer 10

Вот моя реализация O (n) для этого. Я использую массив изменений для расчета максимальной прибыли и дат покупки и продажи. Ваши комментарии приветствуются.

#include<stdafx.h>
#include<stdio.h>

int main()
{
    //int arr[10] = {15, 3, 5,9,10,1,6,4,7,2};
    int arr[7] = {55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};
    int change[7];
    int n=7;
    for(int i=1;i<=n;i++)
    {
    change[i] = arr[i]- arr[i-1];
    }
    int i=0,index = 0;
    int sum = 0;
    int maxsum = 0;
    int startpos = 0;
    int endpos = 0;
    while(index < n)
    {
        sum = sum + change[index];
        if(maxsum < sum)
        {
        maxsum = sum; 
        startpos = i;
        endpos = index;

        }
        else if (sum<0) // negative number ,set sum to zero
        {
        sum = 0;
        i=index+1;
        }
        index++;
    }

    printf("max profit is%d %d %d", maxsum , startpos, endpos+1 );
}