19557

30.08.2021 00:39 •  Информатика

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

ваш старый код
входные данные — массив чисел, каждое из которых отражает цену акции в конкретный день. выходные данные — одно число, обозначающее максимально возможную прибыль.

var maxprofit = function (prices) {
return calculate(prices, 0);
}

function calculate(prices, index) {
if (index > = prices.length) {
return 0;
}

var maxprofix = 0;

for (var start = index; start < prices.length; start++) {
var localmaxprofit = 0;
for (var i = start + 1; i < prices.length; i++) {
if (prices[start] < prices[i]) {
var profit = calculate(prices, i + 1) + prices[i] - prices[start];
if (profit > localmaxprofit) {
localmaxprofit = profit;
}
}
}

if (localmaxprofit > maxprofix)
maxprofix = localmaxprofit;
}
return maxprofix;
}
примеры работы
пример 1
вход: [71,11,51,31,61,41]

выход: 70

покупаем во второй день по цене 11 и продаём на третий день за 51, прибыль — 40. после этого покупаем за 31 в четвёртый день и продаем на пятый за 61, прибыль — 30. в итоге получаем прибыль 70.
пример 2
вход: [13,24,35,46,57]

выход: 44

покупаем в первый день, продаём в последний.
пример 3
вход: [700,612,445,343,10]

выход: 0

здесь вообще невозможно заработать, поэтому максимальная прибыль — 0.

примечания
в качестве решения предоставьте файл, который экспортирует исправленный вариант функции maxprofit:

function maxprofit(prices) {
//
}

module.exports = maxprofit;
решение будет запускаться в nodejs 12.