Вопрос с интервью: максимальная прибыль от нескольких продаж
У меня вопрос по вопросу о алгоритме, который я получил в интервью, и я не могу понять это. Я понимаю, как он должен работать, но не может его сортировать алгоритмически.
Так что предположим, что фирма торгует нефтяными бочками и может сохранить только один нефтяной бочонок за раз. Предположим, что компания знает цену за баррель каждый год в год. Таким образом, он перешел в массив. Как написать алгоритм, чтобы найти, когда покупать и продавать?
Вот пример всего за 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)