Вопрос с интервью: максимальная прибыль от нескольких продаж

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

Так что предположим, что фирма торгует нефтяными бочками и может сохранить только один нефтяной бочонок за раз. Предположим, что компания знает цену за баррель каждый год в год. Таким образом, он перешел в массив. Как написать алгоритм, чтобы найти, когда покупать и продавать?

Вот пример всего за 5 дней для упрощения: 70 74 73 72 76, для дней с понедельника по пятницу соответственно.

Лучше всего здесь купить в понедельник (70) продать во вторник (74), а затем купить в четверг (72) и продать в пятницу (76). Должно ли это подходить рекурсивно? Я действительно хочу это решить.

Спасибо,

Ответ 1

Я предполагаю, что вы хотите максимизировать свою прибыль, верно?

В этом случае вы просто покупаете локальные минимумы и продаете локальные максимумы, что будет простым линейным поиском.

Собственно, все просто. Доказательство:

Обозначим

p(i) ... the price of oil on day i
have(i) ... 1 if we retain the barrel overnight from day i to day i+1, 0 otherwise

определены только для я в [0, N-1]

теперь, если мы купим в день k и продадим в день l, у нас будет

have(k) = 1
have(l) = 0
have(i) = 1 for k < i < l

прибыль будет

p(l)-p(k) = sum over {i from k to l-1} (p(i+1)-p(i))

Обозначим

M(i) = max(p(i+1) - p(i), 0)

Для всех возможных булевых функций have имеем

profit(have) = sum over {i where have(i)==1} (p(i+1) - p(i))
 <= sum over {i where have(i)==1} max(p(i+1) - p(i), 0)
 <= sum over {i where have(i)==1} M(i)
 <= sum over {i in [0, N-1]} M(i)

Вторая строка исходит из того, что max(x, 0) >= x, третья простая переписывается в терминах M(i), четвертая - от M(i) >= 0.

Теперь, если мы установим have(i) == (p(i+1)>p(i)), он будет иметь ту же прибыль, что и выше, что означает, что она максимальна. Кроме того, это означает, что вы покупаете на локальных минимумах и продаете на локальных максимумах.

Ответ 2

Алгоритм в O (N) времени и O (1) пространстве:

Starting at index 0
If you haven't bought an oil barrel:
    if price[i] < price[i + 1], buy at price[i]
    // if price[i] >= price[i + 1], you will never buy at price[i]
    // as price[i + 1] can bring you more money. So just wait...
If you have bought an oil barrel:
    if price[i] > price[i + 1], sell at price[i]
    // if price[i] <= price[i + 1], you will never sell at price[i]
    // as price[i + 1] can bring you more money. So just wait...

Реализация С++:

#include <iostream>
#include <vector>

int best_profit(const std::vector<int>& prices)
{
  bool buying = true;
  int buying_price = 0;
  int profit = 0;

  for(std::vector<int>::size_type i = 0; i < prices.size() - 1; ++i)
  {
    if(buying)
    {
      if(prices[i] < prices[i + 1])
      {
        buying_price = prices[i];
        buying = false;
      }
    }
    else if(prices[i] > prices[i + 1])
    {
      profit += prices[i] - buying_price;
      buying = true;
    }
  }

  if(!buying) // The last price is the highest one!
  {
    profit += prices[prices.size() - 1] - buying_price;
  }

  return profit;
}

int main()
{
  std::vector<int> prices1{1};
  std::vector<int> prices2{1, 2};
  std::vector<int> prices3{3, 2};
  std::vector<int> prices4{70, 74, 73, 72, 76};
  std::vector<int> prices5{70, 75, 71, 80, 96, 100, 15, 50, 60};

  std::cout << "prices1: " << best_profit(prices1) << std::endl;
  std::cout << "prices2: " << best_profit(prices2) << std::endl;
  std::cout << "prices3: " << best_profit(prices3) << std::endl;
  std::cout << "prices4: " << best_profit(prices4) << std::endl;
  std::cout << "prices5: " << best_profit(prices5) << std::endl;
}

Вывод:

prices1: 0
prices2: 1
prices3: 0
prices4: 8
prices5: 79

Ответ 3

Продавайте на локальных максимумах, покупайте у локальных минимумов. Относитесь к цене, прежде чем начинать как бесконечность, и после того, как закончите с нуля.

Ответ 4

Принимая ваш пример или цены на бочку: [70, 74, 73, 72, 76].

Из данных цен я могу вычислить ежедневное изменение цены (т.е. сегодня цена - цена предыдущего дня). "Массив изменения цены" в этом случае будет [4, -1, -1, 4].

В "матрице изменения цены" положительное число означает, что цена увеличилась, а отрицательное число означает, что цена снизилась по сравнению с предыдущим днем.

Решение состоит в том, чтобы найти все смежные подмассивы из "массива изменения цены", которые содержат только положительные числа.

Используя эту идею, я написал ниже код python для печати пар покупки и соответствующих дней продажи:

barrel_price = [70, 74, 73, 72, 76]
trading_days = {} #dictionary for storing {buy_day: sell_day}
buy_day=0
sell_day=buy_day+1

while sell_day < len(barrel_price):
    if barrel_price[sell_day]-barrel_price[sell_day-1]>0:
        #don't sell if price is still increasing
        sell_day=sell_day+1
        trading_days[buy_day] = sell_day-1
    else:
        #don't buy if price is still decreasing
        buy_day=sell_day
        sell_day=buy_day+1

print trading_days

Отпечаток "{0: 1, 3: 4}" Для первой пары 0: 1, т.е. День покупки 0 и день продажи 1, соответствующие цены составляют 70 и 74 в массиве barrel_price. Для следующей пары 3: 4 соответствующая цена покупки составляет 72, а продажная цена - 76.

Ответ 5

L [j] представляет прибыль до j-го дня.
L [j] = L [j-1] + MAX (0, P _j -P _j-1)
P _j= цена акций на j день.
Решение лежит в L [n], так как каждый L [j] дает максимальную прибыль, полученную до этой точки, а L [n] дает максимальную прибыль, полученную до последнего дня.
Время выполнения: O (n)

Ответ 6

просто сравните цены:

найдите самую низкую цену за неделю

(loop1)

(if currentPrice < nextPrice) 
currentPrice = nextPrice

и получите самую высокую цену между текущей ценой (date) и nextLowerSellPrice

(loop2)

(if currentHighPrice<nextHighPrice)
currentHighPrice = nextHighPrice
else
sell(currentHighPriceDay)