Коля изобрёл машину времени у себя в гараже и решил на этом заработать. но так как он знает, что организация контроля времени может забрать у него машину, он решил вести себя осторожнее и использовать рынок ценных бумаг в качестве источника дохода.
он отправился в будущее, посмотрел там котировок по акциям компании 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.

program calklin;

uses

 crt;

var

 a, b, x: real;

begin

 textcolor(red);

 gotoxy(10, 5);

 write('Вас приветствует калькулятор решать линейные уравнения');

 gotoxy(10, 6);

 write('Введите а=');

 readln(a);

 gotoxy(10, 7);

 write('Введите b=');

 readln(b);

 gotoxy(10, 8);

 if a = 0

 then

 begin

   gotoxy(10, 9);

   textcolor(red);

   writeln('Нет корней')

 end

 else

 begin

   if a <> 0

   then

   begin

     gotoxy(10, 10);

     textcolor(red);

     x := (-b / a);

     writeln('Уравнение имеет корень и он равен: x =', x, '');

   end;

 end;

end.

// operations_array.cpp: определяет точку входа для консольного приложения.

#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

int main(int argc, char* argv[])
{
srand(time(NULL));
setlocale(LC_ALL, "rus");
int length_array;
cout << "Укажите количество элементов массива: ";
cin >> length_array;

float *arrayPtr = new float [length_array]; // одномерный динамический массив

// заполняем одномерный массив случайными числами
for (int counter = 0; counter < length_array; counter++)
{
arrayPtr[counter] = - 5.00 + ((rand() % 101) / 10.0); // генерируем случайные числа [-5, 5]
cout << arrayPtr[counter] << " "; // вывод сгенерированного числа
}
cout << endl;

float min = arrayPtr[0]; // инициализируем первым элементом массива
int number_min = 0; // номер минимального элемента
for (int counter = 0; counter < length_array; counter++)
{
if (min > arrayPtr[counter])
{
min = arrayPtr[counter]; // минимальный элемент
number_min = counter; // номер минимального элемента
}
}
cout << "номер минимального элемента = " << (number_min + 1) << endl; // номер минимального элемента

double product = 1;
for (int counter = 0; counter < length_array; counter++)
{
if (arrayPtr[counter] < 0) // находим первое отрицательное число
{
counter++; // переключаемся на следующий элемент
while (arrayPtr[counter] > 0) // пока не нашли второе отрицательное число
{
product *= arrayPtr[counter]; // накапливаем произведение элементов
counter++;
}
break; // выход из цикла for
}
}
cout << "произведение = " << product << endl;

float *relocation_arrayPtr = new float [length_array]; // одномерный динамический массив для перестановок
int index = 0; // индекс массива перестановок

// заполняем массив элементами, модуль которых не превышает 1
for (int counter = 0; counter < length_array; counter++)
{
if (abs(arrayPtr[counter]) <= 1)
{
relocation_arrayPtr[index] = arrayPtr[counter];
index++;
}
}

// заполняем массив элементами, модуль которых больше 1
for (int counter = 0; counter < length_array; counter++)
{
if (abs(arrayPtr[counter]) > 1)
{
relocation_arrayPtr[index] = arrayPtr[counter];
index++;
}
}

// напечатать преобразованный массив
cout << "\nПреобразованный массив:\n";
for (int counter = 0; counter < length_array; counter++)
{
cout << relocation_arrayPtr[counter] << " ";
}
cout << endl;

// высвобождение памяти отводимой под одномерный динамический массив:
delete [] arrayPtr;
delete [] relocation_arrayPtr;
system("pause");
return 0;