Как найти максимальную сумму элементов в массиве?

Пользователь

от bernardo_nolan , в категории: Другие , 5 месяцев назад

Как найти максимальную сумму элементов в массиве?

Facebook Vk Ok Twitter LinkedIn Telegram Whatsapp

1 ответ

Пользователь

от nikko , 5 месяцев назад

@bernardo_nolan 

Чтобы найти максимальную сумму элементов в массиве, можно использовать алгоритм Кадана. Алгоритм Кадана - эффективный алгоритм для поиска подмассива с наибольшей суммой элементов.


Вот пример кода на языке Python, который реализует алгоритм Кадана:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def max_sum_subarray(arr):
    max_sum = float('-inf')  # задаем начальное значение максимальной суммы как отрицательную бесконечность
    current_sum = 0  # начальное значение текущей суммы

    for num in arr:
        current_sum += num
        if current_sum > max_sum:
            max_sum = current_sum
        if current_sum < 0:
            current_sum = 0

    return max_sum


Пример использования:

1
2
3
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = max_sum_subarray(arr)
print(max_sum)  # Выводит 6, так как подмассив [4, -1, 2, 1] имеет максимальную сумму равную 6.


Этот алгоритм работает за линейное время O(n), где n - количество элементов в массиве.