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

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

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

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

Brute force

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

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

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

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

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

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

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

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

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

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

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

Подсчет кол-ва нулевых подмассивов

Март 21, 2023 г.

Разбор задачи с литкода. (2348. Number of Zero-Filled Subarrays). Суть: есть массив чисел, нужно подсчитать кол-во подмассивов, состоящих из нулей. Например, дан массив [0, 0, 1]. Как видим, есть последовательность из двух нулей в начале ...

Читать

Поиск выхода из лабиринта

Июнь 3, 2023 г.

Продолжаем разбор классических задач по программированию. На этот раз лабиринтовая задача, которая формулируется так - дан плоский лабиринт в виде двумерного массива, где стенка отмечена 1, а свободный участок как 0. Также дана начальная позиция игрока, ...

Читать

 

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

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



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