Максимальная сумма элементов подмассива: примеры на Python

Как найти максимальную сумму подмассива, перебирая все возможные подмассивы?

Самый простой способ - проверить каждый возможный подмассив. Временная сложность O(n^3) или O(n^2) при оптимизации. Этот подход подходит для небольших массивов, когда важна простота реализации.

def max_subarray_bruteforce(arr):
    n = len(arr)
    max_sum = float('-inf')
    for i in range(n):
        for j in range(i, n):
            current_sum = 0
            for k in range(i, j+1):
                current_sum += arr[k]
            if current_sum > max_sum:
                max_sum = current_sum
    return max_sum

алгоритмы и структуры данных python (алгоритмы и структуры данных в python)

Оптимизированная версия с накоплением суммы:

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

примеры линейных алгоритмов на python (примеры линейных алгоритмов на python)

Цель использования: образовательная, для понимания задачи.

Как использовать префиксные суммы для нахождения максимальной суммы подмассива?

Предварительно вычисленные префиксные суммы позволяют быстро находить сумму любого подмассива. Однако перебор всех пар i, j даёт O(n^2). Можно улучшить до O(n) с использованием дополнительных структур (например, дерево отрезков), но в простом виде метод не превосходит алгоритма Кадане.

def max_subarray_prefix(arr):
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + arr[i]
    max_sum = float('-inf')
    for i in range(n):
        for j in range(i, n):
            current_sum = prefix[j+1] - prefix[i]
            if current_sum > max_sum:
                max_sum = current_sum
    return max_sum

типы алгоритмов в python (типы алгоритмов в python)

Цель использования: когда требуется также быстро отвечать на запросы суммы произвольного подмассива (после предварительной обработки).

Как применить рекурсивное деление массива для поиска максимальной суммы?

Метод разделяй и властвуй рекурсивно делит массив пополам, находит максимальную сумму в левой, правой части и в подмассиве, пересекающем середину. Временная сложность O(n log n).

def cross_sum(arr, l, m, r):
    left_sum = float('-inf')
    total = 0
    for i in range(m, l-1, -1):
        total += arr[i]
        if total > left_sum:
            left_sum = total
    right_sum = float('-inf')
    total = 0
    for i in range(m+1, r+1):
        total += arr[i]
        if total > right_sum:
            right_sum = total
    return left_sum + right_sum

def max_subarray_dc(arr, l, r):
    if l == r:
        return arr[l]
    m = (l + r) // 2
    left = max_subarray_dc(arr, l, m)
    right = max_subarray_dc(arr, m+1, r)
    cross = cross_sum(arr, l, m, r)
    return max(left, right, cross)

Цель использования: демонстрация парадигмы разделяй и властвуй, а также в задачах, где требуется параллельная обработка.