Поиск Максимального подмассива (по сумме чисел, алгоритм Кадана) - разбор решения алгоритмической задачи

Задача: Maximum Subarray (Максимальный подмассив)

Условие:

дан целочисленный массив nums. Нужно найти непрерывный подмассив (содержащий хотя бы один элемент), сумма элементов которого максимальна, и вернуть эту сумму.

Основная идея

Решение, предложенное Джеем Кадане (Joseph Born Kadane) в 1984 году:

• 1) Будем вычислять все частичные суммы для каждого очередного считываемого числа, сохраняя максимальную
• 2) Если окажется, что очередной элемент уменьшается при сложении с уже накопленной текущей частичной суммой, то будем считать очередной частичной суммой сам этот элемент (фактически - отбрасываем префикс)

Возможная реализация в коде

Например в golang:

package main

import "fmt"

func maxSubArraySum(nums []int) int {
	// Инициализируем переменные первым элементом массива
	maxSum := nums[0]
	currentSum := nums[0]

	// Проходим по массиву, начиная со второго элемента
	for i := 1; i < len(nums); i++ {
		// Выбираем: прибавить текущее число
		// к накопленной сумме
		// или начать заново с текущего числа
		if nums[i] > currentSum+nums[i] {
			// начинаем с нового числа
			currentSum = nums[i]
		} else {
			// накапливаем частичную сумму
			currentSum = currentSum + nums[i]
		}

		// Обновляем глобальный максимум,
		// если текущая сумма стала больше
		if currentSum > maxSum {
			maxSum = currentSum
		}
	}

	return maxSum
}

func main() {
	nums := [][]int{
		{-2, 1, -3, 4, -1, 2, 1, -5, 4},
		{-2, 3, -1},
		{3, -2, 3, -1},
		{-1, -2, -1},
		{1, 1, -2},
	}

	for _, test := range nums {
		fmt.Printf("Максимальная сумма: %d\n",
			maxSubArraySum(test))
	}
}

Анализ сложности

O(N) линейная сложность по чтению элементов массива (за один проход) + всего две допонительные переменные по памяти, т.е. O(1) по памяти

Дополнительные материалы

1. Поиск подотрезка массива с максимальной/минимальной суммой, разбор самих алгоритмов: http://e-maxx.ru/algo/maximum_average_se...