Алгоритмы и структуры данных

Алгоритм Кадане

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

Алгоритм:
1. Инициализируйте переменные maxendinghere и maxsofar равными первому элементу массива.
2. Пройдитесь по всем элементам массива, начиная со второго элемента.
3. Для каждого элемента, вычислите maxendinghere как максимум из текущего элемента и суммы текущего элемента и maxendinghere.
4. Если maxendinghere больше maxsofar, обновите maxsofar.
5. Повторите шаги 3-4 для всех элементов массива.
6. Верните значение maxsofar, которое будет содержать максимальную сумму подмассива.

Сложность: O(n), где n – количество элементов в массиве.

www.tgoop.com/the_algorithms/4622

5.9K viewsedited  Dec 5, 2023 at 09:05

Алгоритм Кадане

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

Алгоритм:
1. Инициализируйте переменные maxendinghere и maxsofar равными первому элементу массива.
2. Пройдитесь по всем элементам массива, начиная со второго элемента.
3. Для каждого элемента, вычислите maxendinghere как максимум из текущего элемента и суммы текущего элемента и maxendinghere.
4. Если maxendinghere больше maxsofar, обновите maxsofar.
5. Повторите шаги 3-4 для всех элементов массива.
6. Верните значение maxsofar, которое будет содержать максимальную сумму подмассива.

Сложность: O(n), где n – количество элементов в массиве.

BY Алгоритмы и структуры данных