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

Метод 1: подход грубой силы

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

def find_max_subarray_brute_force(arr, start, end):
    max_sum = float('-inf')
    for i in range(start, end + 1):
        for j in range(i, end + 1):
            subarray_sum = sum(arr[i:j+1])
            max_sum = max(max_sum, subarray_sum)
    return max_sum

Метод 2: динамическое программирование (алгоритм Кадане)

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

def find_max_subarray_kadane(arr, start, end):
    max_sum = arr[start]
    current_sum = arr[start]
    for i in range(start + 1, end + 1):
        current_sum = max(arr[i], current_sum + arr[i])
        max_sum = max(max_sum, current_sum)
    return max_sum

Метод 3. Разделяй и властвуй

Подход «разделяй и властвуй» рекурсивно делит массив на более мелкие подмассивы и объединяет результаты для поиска максимального подмассива. Его временная сложность равна O(n log n).

def find_max_subarray_divide_conquer(arr, start, end):
    if start == end:
        return arr[start]
    mid = (start + end) // 2
    left_max = find_max_subarray_divide_conquer(arr, start, mid)
    right_max = find_max_subarray_divide_conquer(arr, mid + 1, end)
    left_sum = float('-inf')
    sum_val = 0
    for i in range(mid, start - 1, -1):
        sum_val += arr[i]
        left_sum = max(left_sum, sum_val)
    right_sum = float('-inf')
    sum_val = 0
    for i in range(mid + 1, end + 1):
        sum_val += arr[i]
        right_sum = max(right_sum, sum_val)
    return max(left_max, right_max, left_sum + right_sum)

Метод 4: скользящее окно

Техника скользящего окна полезна, когда подмассив должен быть непрерывным. Он поддерживает окно элементов и перемещает его по массиву, обновляя максимальную сумму по мере продвижения. Временная сложность этого подхода составляет O(n).

def find_max_subarray_sliding_window(arr, start, end):
    max_sum = float('-inf')
    current_sum = 0
    left = start
    for right in range(start, end + 1):
        current_sum += arr[right]
        max_sum = max(max_sum, current_sum)
        if current_sum < 0:
            current_sum = 0
            left = right + 1
    return max_sum

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