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

Методы:

1. Метод грубой силы:
   Подход грубой силы включает в себя проверку всех возможных подмассивов и вычисление их сумм. Затем максимальная сумма определяется путем сравнения сумм всех подмассивов. Хотя этот метод имеет временную сложность O(n^3), он обеспечивает простое решение. Вот код:

def find_maximum_sum_brute_force(arr):
    n = len(arr)
    max_sum = float('-inf')
    for i in range(n):
        for j in range(i, n):
            current_sum = sum(arr[i:j+1])
            max_sum = max(max_sum, current_sum)
    return max_sum

1. Алгоритм Кадане:
   Алгоритм Кадане – это эффективный подход к поиску максимальной суммы подмассива. Он работает путем перебора массива и поддержания текущей суммы. Если текущая сумма становится отрицательной, она сбрасывается в ноль. Максимальная сумма отслеживается на протяжении всей итерации. Алгоритм Кадане имеет временную сложность O(n). Вот код:

def find_maximum_sum_kadane(arr):
    max_sum = float('-inf')
    current_sum = 0
    for num in arr:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

1. Динамическое программирование.
   Динамическое программирование обеспечивает элегантное решение этой проблемы. Он включает в себя построение таблицы для хранения максимальной суммы по каждому индексу. Рассмотрев два случая — либо расширение подмассива, либо создание нового подмассива — мы можем вычислить максимальную сумму с любого конца. Динамическое программирование имеет временную сложность O(n). Вот код:

def find_maximum_sum_dynamic(arr):
    n = len(arr)
    max_sum = arr[0]
    max_ending_here = arr[0]
    max_so_far = arr[0]
    for i in range(1, n):
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        max_sum = max(max_sum, max_ending_here)
        max_so_far = max(max_so_far, arr[i])
    return max(max_sum, max_so_far)