Предположим, вы инвестируете в компанию, которой известны прошлые цены на акции, и все, что вам нужно, это максимизировать свою прибыль ...
Естественно, в этом случае первое, что приходит в голову, - это либо покупка акций по самой низкой цене, либо продажа их по самой высокой цене. Для этого мы можем сначала найти самые низкие и самые высокие цены, а затем
- Начните с самой низкой цены и двигайтесь вправо, пока не найдете самую высокую цену после самой низкой цены и вычислите прибыль.
- Начните с наивысшей цены и двигайтесь влево, пока не найдете самую низкую цену перед самой высокой ценой и вычислите прибыль.
- Получите максимум из двух вышеперечисленных.
Но так бывает не всегда. Давайте посмотрим на следующий встречный пример.
В этом примере самая высокая и самая низкая цена - 11 и 6 соответственно. Так,
- Если мы начнем с самой низкой цены (6) и пойдем вправо, пока не найдем самую высокую цену после самой низкой цены, мы ее не найдем. (6 - цена акции на последний день)
- Если мы начнем с самой высокой цены (11) и пойдем влево, пока не найдем самую низкую цену перед самой высокой, мы найдем 10, а прибыль будет равна 1.
- Сравнивая вышеизложенное, мы получим 1 как максимальную прибыль.
Но это неправильно! Мы можем заработать 3 прибыли, если посмотрим глубже ??
Да! Покупая акции после 2-го дня по цене 7 и продавая их после 3-го дня по цене 10, мы получим прибыль в размере 3 на акцию.
Из приведенного выше примера вы можете понять, что наш подход не работает.
Так как же решить эту проблему и найти максимальную прибыль? Что ж, для этого нам нужно немного по-другому взглянуть на эту проблему. Нам нужно найти последовательность дней, в течение которых чистое изменение с первого дня до последнего является максимальным.
Давайте преобразуем вышеуказанный массив, как мы только что упомянули. Поэтому нам нужно учитывать ежедневное изменение цены, а не дневные цены.
Нам нужно найти последовательность дней, в течение которой чистое изменение с первого дня до последнего является максимальным. Вот где возникает проблема с подмассивом максимальной суммы!
Для массива «A» найдите подмассив максимальной суммы и соответствующую сумму.
Ну вот тут и описано решение!
Начните с левого конца массива и продвигайтесь вправо, отслеживая максимальный подмассив, видимый на данный момент. Зная максимальный подмассив A [1..j], расширьте ответ, чтобы найти максимальный подмассив, заканчивающийся индексом
j + 1, используя следующее наблюдение.
- Максимальный подмассив A [1..j + 1] является либо максимальным подмассивом A [1..j], либо подмассивом A [i..j + 1] для некоторого 1≤ i≤ j + 1.
Псевдокод для вышеуказанного алгоритма ниже.
FIND_MAX_SUBARRAY (A)
start = 0
end = 0
max_so_far = 0
max_end = 0
for i= 1 to A.length
max_end = max_end + A[i]
max_end = max(max_end,0)
if (max_end-A[i]==0) then start = i
if (max_so_far < max_end) then (max_so_far = max_end & end = i)
return (start, end, max_so_far)
Объяснение
В приведенном выше алгоритме индекс массива начинается с 1. В первой и второй строках приведенного выше алгоритма я инициализировал переменные начала и конца. Эти переменные представляют собой начальный и конечный индексы максимального подмассива.
В третьей строке «max_so_far» - максимальная сумма, наблюдаемая на данный момент. А в четвертой строке «max_end» - максимальная сумма, заканчивающаяся на текущем элементе списка «A».
С пятой строки по девятую мы перебираем массив. В шестой строке мы добавляем каждый новый элемент к max_end, а с седьмой строки мы приравниваем max_end к нулю (0), если он отрицательный. Когда «max_end» таким образом становится равным нулю, это означает начало нового потенциального максимального подмассива. Итак, в восьмой строке мы обновляем переменную «start», чтобы указать это.
В девятой строке, если максимальная видимая сумма меньше, чем «max_end», мы обновляем «max_so_far», чтобы он по-прежнему представлял максимальную сумму. Также мы обновляем переменную «end», чтобы она представляла конечный индекс текущего максимального подмассива.
В последней строке приведенный выше алгоритм возвращает начальный и конечный индексы подмассива максимальной суммы и максимальной суммы.
Вышеупомянутый алгоритм работает в линейном времени и известен как алгоритм Кадана !. Это тоже не рекурсивно!