Задача о поиске лучшей сделки

Это еще одна классическая задача программирования о поиске некой лучшей пары чисел в массиве. Задача формулируется следующим образом.

Есть массив стоимости актива по дням, необходимо найти оптимальные точки покупки и продажи актива (входа и выхода из сделки). Обычно требуется найти максимальную величину прибыли в рамках периода, за который предоставлены данные.

Рассмотрим произвольные данные биржевой динамики актива. Мне кажется, и без вычислений очевидно, где здесь точки входа и выхода. Это будут M1 и X2.

Brute force

Если решать эту задачу «грубой силой», нам нужно перебрать все элементы массива слева направо (i), и для каждого из них вычислять разницу с оставшимися элементами справа (j). Максимальная дельта и будет искомой величиной.

Ясно, что уже даже для массива в 10000 элементов, такие вычисления потребует времени, так мы перебираем элементы вложенными циклами. Число вычислений в цикле составит порядка N * N / 2.

Местные экстремумы

Совершенно ясно также, что для каждой точки массива, нас интересуют только самая минимальная величина актива слева от точки и максимальная величина справа от точки. И мы можем вычислить эти величины за один проход цикла.

Еще один проход цикла позволит найти максимум разницы между минимумами и максимумами в каждой точке. Т.е. число итераций циклов составит порядка 2 * N.

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

Поиск максимума

На самом деле мы делаем очень много лишних вещей, так как выполнить задачу можно с затратами порядка N и не создавая лишних массивов.

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

Написать комментарий

Мало букафф? Читайте есчо !

Поиск самой длинной петли в графе

Март 26, 2023 г.

Как говорили учителя в школе - а теперь для самых умных задача со звездочкой. "Longest cycle in a graph" отмечена как сложная задача на leetcode. Давайте разберем как её решить. Дан массив, который описывает ориентированный граф. В каждой ячейке ...

Читать

GreyCode генератор

Май 3, 2023 г.

Задачи с бинарными последовательностями мне очень нравятся из-за их "эвристичности". Решение часто скрывается в двух шагах, но додуматься не просто. Следующая задача описывается так - нужно сгенерировать n-разрядный "серый код". Если вы не ...

Читать

 

Комментарии к «Задача о поиске лучшей сделки»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: