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

def max_subsequence_sum_brute_force(arr):
    max_sum = float('-inf')
    for i in range(len(arr)):
        curr_sum = 0
        for j in range(i, len(arr)):
            curr_sum += arr[j]
            if curr_sum > max_sum:
                max_sum = curr_sum
    return max_sum

2. Алгоритм Кадане.
   Алгоритм Кадане – это эффективный метод, который решает задачу о максимальной сумме подмассивов с линейной временной сложностью. Он использует принципы динамического программирования для нахождения максимальной суммы подпоследовательности. Идея состоит в том, чтобы отслеживать максимальную сумму, заканчивающуюся в каждой позиции, и обновлять ее при проходе по массиву. Вот пример кода:

def max_subsequence_sum_kadane(arr):
    max_sum = arr[0]
    curr_sum = arr[0]
    for i in range(1, len(arr)):
        curr_sum = max(arr[i], curr_sum + arr[i])
        max_sum = max(max_sum, curr_sum)
    return max_sum

3. Разделяй и властвуй.
   Подход «разделяй и властвуй» делит массив на две половины и рекурсивно находит максимальную сумму подпоследовательности в каждой половине. Затем он объединяет результаты, чтобы найти максимальную сумму для обеих половин. Вот пример кода:

def max_subsequence_sum_divide_conquer(arr, low, high):
    if low == high:
        return arr[low]
    mid = (low + high) // 2
    left_sum = float('-inf')
    sum = 0
    for i in range(mid, low - 1, -1):
        sum += arr[i]
        left_sum = max(left_sum, sum)
    right_sum = float('-inf')
    sum = 0
    for i in range(mid + 1, high + 1):
        sum += arr[i]
        right_sum = max(right_sum, sum)
    return max(left_sum + right_sum, max_subsequence_sum_divide_conquer(arr, low, mid), max_subsequence_sum_divide_conquer(arr, mid + 1, high))

4. Динамическое программирование.
   Динамическое программирование также можно использовать для решения проблемы максимальной суммы подпоследовательности, отслеживая максимальную сумму, обнаруженную на данный момент. Вот пример кода:

def max_subsequence_sum_dynamic(arr):
    max_sum = arr[0]
    curr_sum = arr[0]
    for i in range(1, len(arr)):
        curr_sum = max(arr[i], curr_sum + arr[i])
        max_sum = max(max_sum, curr_sum)
    return max_sum

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