Я вторгаюсь в эту древнюю ветку, чтобы дать подробное объяснение того, почему алгоритм Кадане работает. Алгоритм был представлен в классе, в котором я сейчас учусь, но только с неопределенным объяснением. Вот реализация алгоритма в Haskell:
maxCont l = maxCont' 0 0 l
maxCont' maxSum _ [] = maxSum
maxCont' maxSum thisSum (x:xs)
| newSum > maxSum = maxCont' newSum newSum xs
| newSum < 0 = maxCont' maxSum 0 xs
| otherwise = maxCont' maxSum newsum xs
where
newSum = thisSum + x
Теперь, поскольку мы просто пытаемся понять алгоритм, давайте отменим небольшую оптимизацию имен newSum:
maxCont l = maxCont' 0 0 l
maxCont' maxSum _ [] = maxSum
maxCont' maxSum thisSum (x:xs)
| thisSum + x > maxSum = maxCont' (thisSum + x) (thisSum+x) xs
| thisSum + x < 0 = maxCont' maxSum 0 xs
| otherwise = maxCont' maxSum (thisSum+x) xs
Что это за безумная функция maxCont'? Давайте придумаем простую спецификацию того, что он должен делать. Мы хотим, чтобы выполнялось следующее с условием, что 0 ≤ thisSum ≤ maxSum:
maxCont' maxSum thisSum [] = maxSum
maxCont' maxSum thisSum l = maximum [maxSum, thisSum + maxInit l, maxCont l]
, где maxInit l - наибольшая сумма начального сегмента l, а maxCont - максимальная непрерывная сумма l.
Тривиальный, но важный факт: для всех l, maxInit l ≤ maxCont l. Должно быть очевидно, что приведенная выше спецификация гарантирует maxCont l = maxCont' 0 0 l, чего мы и хотим. Вместо того, чтобы пытаться объяснить, почему окончательная версия maxCont 'реализует приведенную выше спецификацию (которую я не знаю, как это сделать), я покажу, как ее можно извлечь из нее, преобразовывая спецификацию по одному шагу за раз, пока это становится кодом, который тогда, безусловно, будет правильным. Как написано, эта спецификация не дает реализацию: если maxCont определен в терминах maxCont', как описано выше, он будет зацикливаться вечно, поскольку maxCont' вызывает maxCont, вызывает maxCont' с тем же списком. Итак, давайте немного расширим его, чтобы показать фрагменты, которые нам понадобятся:
maxCont' maxSum thisSum (x:xs) =
maximum [maxSum, thisSum + maxInit (x:xs), maxCont (x:xs)]
Это еще ничего не исправило, но разоблачило вещи. Давайте использовать это. thisSum + maxInit (x:xs) это либо thisSum, либо thisSum + x + maxInit xs. Но thisSum ≤ maxSum по предварительному условию, поэтому мы можем игнорировать эту возможность при расчете максимума. maxCont (x:xs) - это сумма, которая либо включает x, либо не включает. Но если он включает x, то он такой же, как maxInit (x:xs), который описан в предыдущем пункте, поэтому мы можем игнорировать эту возможность и рассматривать только случай, когда maxCont (x:xs) = maxCont xs. Итак, мы приходим к следующей версии:
maxCont' maxSum thisSum (x:xs) = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]
Этот, наконец, правильно рекурсивный, но у нас есть способы добраться до эффективного кода, особенно потому, что мифический maxInit будет слишком медленным. Давайте разберем его на три случая, рассмотренные в коде Java (немного злоупотребляя нотацией на Haskell):
maxCont' maxSum thisSum (x:xs)
| maxSum < thisSum + x = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]
| thisSum + x < 0 = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]
| 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]
В первом случае мы знаем, что maxSum не может быть максимумом: thisSum+x больше, а maxInit xs всегда положительно. Во втором случае мы знаем, что thisSum+x+maxInit xs не может быть максимумом: maxCont xs всегда по меньшей мере равен maxInit xs, а thisSum+x отрицательно. Таким образом, мы можем исключить эти возможности:
maxCont' maxSum thisSum (x:xs)
| maxSum < thisSum + x = maximum [ thisSum+x+maxInit xs, maxCont xs]
| thisSum + x < 0 = maximum [maxSum, maxCont xs]
| 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]
Теперь у нас едва хватает края, чтобы закручивать вещи вокруг. Теперь, когда мы исключили невозможные случаи, мы собираемся добавить несколько дублирующих случаев, которые вернут эти три случая в одну и ту же форму, чтобы мы могли заменить исходную спецификацию maxCont'. В первом случае у нас нет первого термина, поэтому нам нужно использовать то, что, как мы знаем, не превысит другие термины. Чтобы сохранить инвариант, равный thisSum ≤ maxSum, нам нужно будет использовать thisSum+x. Во втором случае у нас нет второго члена, который выглядит как something+maxInit xs, но мы знаем, что maxInit xs ≤ maxCont xs, поэтому мы можем смело придерживаться 0+maxInit xs. Добавление этих дополнительных терминов для регулярности приводит к следующему:
maxCont' maxSum thisSum (x:xs)
| maxSum < thisSum + x = maximum [(thisSum+x), (thisSum+x)+maxInit xs, maxCont xs]
| thisSum + x < 0 = maximum [maxSum, 0+maxInit xs, maxCont xs]
| 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]
Наконец, проверив предварительное условие, подставляем в спецификацию
maxCont' maxSum thisSum l = maximum [maxSum, thisSum + maxInit l, maxCont l]
чтобы получить
maxCont' maxSum thisSum (x:xs)
| maxSum < thisSum + x = maxCont' (thisSum+x) (thisSum+x) xs
| thisSum + x < 0 = maxCont' maxSum 0 xs
| 0 ≤ thisSum + x ≤ maxSum = maxCont' maxSum (thisSum+x) xs
Исправление этого в реальном синтаксисе и привязка к пропущенному базовому случаю дает действительный алгоритм, который, как мы теперь доказали, удовлетворяет спецификации, пока он завершается. Но каждый последующий рекурсивный шаг работает с более коротким списком, поэтому он действительно завершается.
Ради меня, напоследок, еще одна вещь, которая заключается в более идиоматическом и гибком написании окончательного кода:
maxCont :: (Num a, Ord a) => [a] -> a
maxCont = fst . foldl maxCont' (0,0)
where
maxCont' (maxSum, thisSum) x
| maxSum < newSum = (newSum, newSum)
| newSum < 0 = (maxSum, 0)
| otherwise = (maxSum, newSum)
where newSum = thisSum + x