Если вы ищете решение Максимального подмассива leetcode или объяснение непрерывного подмассива с наибольшей суммой, также известного как Алгоритм Кадане, то вы попали по адресу.

Постановка задачи: найти сумму наибольшего подмассива в заданном массиве.

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

nums=[5,4,-1,7,8]
max_sum = 0
for i in range(len(nums)):
    current_sum = 0
    for j in range(i,len(nums)):
       current_sum +=nums[j]
       if current_sum>max_sum:
           max_sum = current_sum
print(max_sum)

Подход 2: использование динамического программирования
Рекурсивное отношение для задачи максимального подмассива можно определить следующим образом:
Пусть A — массив из n элементов, и пусть maxSubArray(A, i) — максимальный подмассив, который заканчивается на индексе i в массиве A.
Тогда рекурсивное отношение можно определить как:

maxSubArray(A, i) = max(maxSubArray(A, i - 1) + A[i], A[i])

Это рекурсивное отношение утверждает, что максимальный подмассив, заканчивающийся индексом i, является либо максимальным подмассивом, заканчивающимся индексом i - 1, расширенным элементом A[i], либо просто самим элементом A[i].

Чтобы найти максимальный подмассив всего массива, вы можете использовать следующую рекурсивную функцию:

def maxSubArray(A, i):
  if i == 0:
    return A[0]
  else:
    return max(maxSubArray(A, i - 1) + A[i], A[i])

# To find the maximum subarray of the entire array A:
max_subarray = max(maxSubArray(A, i) for i in range(len(A)))

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

Подход 3:Итеративный + Памятка
В этом решении dp[i] хранит максимум среди суммы всех подмассивов заканчивается индексом i. И тогда мы можем вернуть максимум этого массива dp в качестве ответа.
Мы сохранили значение максимальной суммы в переменной, поэтому нам не нужно отдельно искать максимальный элемент в массиве dp.

nums= [5,4,-1,7,8]

dp = [0]*len(nums)
big = nums[0]
dp[0] = nums[0]
for i in range(1,len(nums)):
    dp[i] = max(dp[i-1]+nums[i],nums[i])
    if dp[i]>big:
        big = dp[i]
print(big)

Временная сложность итеративного решения для задачи максимального подмассива составляет O (n), а пространственная сложность — O (n), поскольку мы используем список dp.

Подход 4: алгоритм Кадане

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

Вот код Python для алгоритма Кадане:

def max_subarray_sum(arr):
    max_sum = float('-inf')
    current_sum = 0
 
    for i in range(len(arr)):
        current_sum += arr[i]
        max_sum = max(max_sum, current_sum)
 
        if current_sum < 0:
            current_sum = 0
 
    return max_sum
 
 
# test the function
arr = [2, 3, 4, 5, 7]
print(max_subarray_sum(arr))

Сканирует массив слева направо, отслеживая максимальный суммарный подмассив, просмотренный до сих пор. Он поддерживает переменную current_sum, которая представляет сумму подмассива, заканчивающегося текущим элементом, и обновляет переменную max_sum максимальным значением max_sum и current_sum. Если current_sum становится отрицательным, он сбрасывается в 0, так как подмассив с отрицательной суммой всегда будет меньше, чем подмассив без элементов.

Временная сложность алгоритма Кадане составляет O(n). Это означает, что для запуска алгоритма потребуется приблизительно линейное время, а пространственная сложность алгоритма Кадане составляет O (1), поскольку он использует только несколько переменных для хранения промежуточных результатов и не создает никаких дополнительных структур данных.