Анализ алгоритма «Нахождение максимальной суммы последующих элементов»

Question

Если возможно, я бы хотел, чтобы кто-то дал аналитическое объяснение алгоритма.

Например, учитывая последовательность

-2, 4, -1, 3, 5, -6, 1, 2 

, максимальная сумма подпоследовательности будет

4 + -1 + 3 + 5 = 11

Этот алгоритм, на который я ссылаюсь, является алгоритмом типа «разделяй и властвуй».

Алгоритм O (nlogn) сложность.

На самом деле я стремлюсь кпосмотрите пример всех шагов, которые производит этот алгоритм.Вышеуказанная последовательность может быть использована для примера.

Answer 1

Идея состоит в том, чтобы разбить вашу последовательность пополам, найти ответы для обеих половин, а затем использовать ее, чтобы найти ответ для всей последовательности.

Предположим, у вас есть последовательность [left, right]. Пусть m = (left + right) / 2. Теперь подпоследовательность максимальной суммы (MSS) [left, right] равна либо MSS(left, m), MSS(m + 1, right), либо последовательности, которая начинается в [left, m] и заканчивается где-то в [m + 1, right].

псевдокод:

MSS(left, right)
  if left = right then return sequence[left]
  m = (left + right) / 2
  leftMSS = MSS(left, m)
  rightMSS = MSS(m + 1, right)

  maxLeft = -inf // find the maximum sum subsequence that ends with m and starts with at least left
  cur = 0
  i = m
  while i >= left do
    cur += sequence[i]
    if cur > maxLeft
      maxLeft = cur

  maxRight = -inf // find the maximum sum subsequence that starts with m + 1 and ends with at most right
  cur = 0
  i = m + 1
  while i <= right
    cur += sequence[i]
    if cur > maxRight
      maxRight = cur

  return max(leftMSS, rightMSS, maxLeft + maxRight)

Это O(n log n), потому что рекурсия три имеет высоту O(log n) и на каждом уровне дерева мы выполняем O(n) работу.

Вот как это будет работать на -2, 4, -1, 3, 5, -6, 1, 2:

 0  1  2 3 4  5 6 7
-2  4 -1 3 5 -6 1 2

                                             MSS(0, 7) = 11
                                      /                    \
                              MSS(0, 3) = 6                 MSS(4, 7) = 5 ------
                          /                  \              |                   \
           MSS(0, 1) = 4                    MSS(2, 3) = 3   MSS(4, 5) = 5      NSS(6, 7) = 3
             /       \                    /              \
   MSS(0, 0) = -2     MSS(1, 1) = 4    MSS(2, 2) = -1    MSS(3, 3) = 3

Интерес представляет вычисление MSS(0, 3) и MSS(0, 7), поскольку они не просто берут максимум своих детей. Для MSS(0, 3) мы стараемся сделать как можно большую сумму, добавляя последовательные элементы, начиная с середины интервала (1) и заканчивая слева. Этот максимум составляет 4. Далее мы делаем то же самое, начиная с середины интервала + 1 и заканчивая направо. Этот максимум составляет 2. Добавление их вместе дает нам подпоследовательность максимальной суммы с суммой 6, которая больше, чем подпоследовательность максимальной суммы двух дочерних интервалов, поэтому вместо этого мы возьмем эту.

Аргументация аналогична MSS(0, 7).

Answer 2

На самом деле это можно сделать за O (n) время, используя алгоритм, называемый алгоритм Кадане .Я написал свою собственную версию и анализ ее сложности , если вам интересно.Идея состоит в том, чтобы использовать динамическое программирование для постепенного улучшения решения, пока не будет найдена оптимальная подпоследовательность.