Коля изобрёл машину времени у себя в гараже и решил на этом заработать. но так как он знает, что организация контроля времени может забрать у него машину, он решил вести себя осторожнее и использовать рынок ценных бумаг в качестве источника дохода.
он отправился в будущее, посмотрел там котировок по акциям компании 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.
// Внимание! Если программа не работает, обновите версию!
begin
var s:=ReadlnString;
var c:=s.ToWords.Where(t->t.Length>1).SelectMany(w->w.Pairwise)
.Select(t->t[0]+t[1]).GroupBy(t->t).Select(t->(t.Key,t.Count))
.OrderByDescending(t->t[1]).ThenByDescending(t->t[0]).First[0];
Writeln('Чаще других встречается цепочка "',c,'"')
end.
Пример
TWAS BRILLIG AND THE SLITHY TOVES DID GYRE AND GIMBLE IN THE WABE ALL MIMSY WERE THE BOROGOVES AND THE MOME RATHS OUTGRABE
Чаще других встречается цепочка "TH"
Замечание: ограничение на длину строки увеличено до 2 млн. символов.
const
N = 5;//Размерность массива
var
m: array[1..N] of integer;
begin
var pr := 1;
for var i := 1 to N do
begin
read(m[i]);
if m[i] <> 0 then pr := pr * m[i];
end;
writeln(pr);
end.
Пример:
Входные данные:
1 2 3 0 5
Выходные данные:
30
2)
const
N = 3;//Размерность матрицы
var
m: array[1..N, 1..N] of integer;
i, j: integer;
rec: record
mmax: integer = -(maxint);
ind: record
i: integer;
j: integer;
end;
end;
begin
for i := 1 to N do
for j := 1 to N do
begin
read(m[i, j]);
if abs(m[i, j]) > rec.mmax then begin
rec.mmax := abs(m[i, j]);
rec.ind.i := i;
rec.ind.j := j;
end;
end;
writeln('Максимальный по модулю элемент матрицы ', rec.mmax, '(', rec.ind.i, ';', rec.ind.j, ')');
end.
Пример:
Входные данные:
1 2 3
4 5 -9
7 8 6
Выходные данные:
Максимальный по модулю элемент матрицы 9(2;3)