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

Естественно, в этом случае первое, что приходит в голову, - это либо покупка акций по самой низкой цене, либо продажа их по самой высокой цене. Для этого мы можем сначала найти самые низкие и самые высокие цены, а затем

  1. Начните с самой низкой цены и двигайтесь вправо, пока не найдете самую высокую цену после самой низкой цены и вычислите прибыль.
  2. Начните с наивысшей цены и двигайтесь влево, пока не найдете самую низкую цену перед самой высокой ценой и вычислите прибыль.
  3. Получите максимум из двух вышеперечисленных.

Но так бывает не всегда. Давайте посмотрим на следующий встречный пример.

В этом примере самая высокая и самая низкая цена - 11 и 6 соответственно. Так,

  1. Если мы начнем с самой низкой цены (6) и пойдем вправо, пока не найдем самую высокую цену после самой низкой цены, мы ее не найдем. (6 - цена акции на последний день)
  2. Если мы начнем с самой высокой цены (11) и пойдем влево, пока не найдем самую низкую цену перед самой высокой, мы найдем 10, а прибыль будет равна 1.
  3. Сравнивая вышеизложенное, мы получим 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)

  1. start = 0
  2. end = 0
  3. max_so_far = 0
  4. max_end = 0
  5. for i= 1 to A.length
  6. max_end = max_end + A[i]
  7. max_end = max(max_end,0)
  8. if (max_end-A[i]==0) then start = i
  9. if (max_so_far < max_end) then (max_so_far = max_end & end = i)
  10. 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», чтобы она представляла конечный индекс текущего максимального подмассива.

В последней строке приведенный выше алгоритм возвращает начальный и конечный индексы подмассива максимальной суммы и максимальной суммы.

Вышеупомянутый алгоритм работает в линейном времени и известен как алгоритм Кадана !. Это тоже не рекурсивно!