Алгоритм Каденса: суміжний підмасив з найбільшою сумою

Яка найбільша суміжна підмасивна суміжна ...

Підмасив — це безперервна частина масиву. Це може бути один елемент масиву або частина масиву. Суміжний підмасив із найбільшою сумою означає підмасив із максимальним сумарним значенням.

Наприклад, візьмемо масив {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Його підмасиви можуть бути {-10, 5, 1, 6}, {5, 1, 6} або {2, -7, 3, -5} тощо. Однак, {5, 1, 6, 3} не може бути підмасивом, оскільки елементи не знаходяться в суміжній послідовності.

Якщо ви помітили, серед усіх підмасивів, виділений підмасив {5, 1, 6} має максимальне значення суми:

Сума підмасиву {5, 1, 6} дорівнює 12, що є максимальною сумою для всіх можливих підмасивів вищенаведеного масиву. Отже, для цього масиву максимальна сума суміжного підмасиву дорівнює {5, 1, 6}.

Простий підхід до розв'язання найбільшої суми неперервного підмасиву

Простий спосіб розв’язати цю задачу — використати два цикли, щоб знайти всі підмасиви, обчислити суму, а потім знайти її максимальне значення.

Ось блок-схема простого підходу до знаходження найбільшої суми неперервних підмасивів. Це метод перебору, оскільки ми проходимо через усі можливі підмасиви.

Ось прості кроки для цього.

Крок 1) форматувати максимальна_сума з мінімальним цілочисельним значенням та набором починати та кінець до нуля.

Крок 2) Дозволяти i та j бути індексами масиву, де j більше або дорівнює i; i позначає початок підмасиву та j його кінець.

Крок 3) поточна_сума містить поточну суму. Після кожного оновлення перевіряйте, чи поточна_сума більше максимальна_сума.

Крок 4) If поточна_сума більший, замініть максимальна_сума з ним.

Крок 5) Коли j досягає кінця масиву, інкремент i і скинути поточна_сума в 0.

Крок 6) Повторюйте, доки i досягає кінця масиву. максимальна_сума тоді містить найбільшу суму підмасиву.

Псевдо Code для простого підходу

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        store the maximum subArray
    return the maximum sum

C++ Реалізація простого підходу

#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
    int max_sum = -1e9;
    int begin = 0;
    int end = 0;
    for (int i = 0; i < n; i++) {
        int current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += array[j];
            if (max_sum < current_sum) {
                max_sum = current_sum;
                begin = i;
                end = j;
            }
        }
    }
    cout << "largest sum is " << max_sum << endl;
    cout << "largest sum contiguous subarray: ";
    for (int i = begin; i <= end; i++) {
        cout << array[i] << "\t";
    }
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}

вихід:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Python Реалізація простого підходу

def maximumSubarraySum(numbers):
    max_sum, begin, end = -1e9, 0, 0
    for i in range(len(numbers)):
        current_sum = 0
        for j in range(i, len(numbers)):
            current_sum += numbers[j]
            if max_sum < current_sum:
                max_sum = current_sum
                begin, end = i, j
    print("largest sum is ", max_sum)
    print("largest sum contiguous subarray: ", end='')
    for i in range(begin, end + 1):
        print(numbers[i], end='\t')

numbers = [-10, 5, 1, 6, -9, 2, -7, 3, -5]
maximumSubarraySum(numbers)

вихід:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Алгоритм Кадане для знаходження найбільшої суми суміжних підмасивів

Алгоритм Кадане — це метод динамічного програмування, який використовує один цикл замість двох. Він обробляє масиви зі змішаними додатними та від'ємними числами, якщо хоча б одне значення є невід'ємним.

Нам потрібно лише дві змінні, щоб знайти найбільшу суму неперервного підмасиву. Ось блок-схема:

Ось кроки для алгоритму Кадане:

Крок 1) Створіть дві змінні, поточна_сума та максимальна_сума.

поточна_сума зберігає максимальну суму, яка закінчується на певному індексі масиву, тоді як максимальна_сума зберігає найбільше значення суми, яке спостерігалося до цього часу.

Крок 2) Додати кожен елемент масиву до поточна_сумаПотім перевірте дві умови нижче:

• If поточна_сума менше, ніж поточний елемент, тоді поточна_сума стає поточним елементом.
• If максимальна_сума менше, ніж поточна_сума, То максимальна_сума стає поточна_сума.

Крок 3) Після повторення попереднього кроку для всього масиву, максимальна_сума містить найбільшу суму суміжного підмасиву.

Приклад алгоритму Кадане

Ми демонструємо алгоритм Кадане на невеликому масиві та розглянемо кожен крок знаходження найбільшої суми неперервного підмасиву.

Припустимо, що заданий масив має такий вигляд:

Ось кроки алгоритму Кадане:

Крок 1) Створіть дві змінні, поточна_сума та максимальна_сумаПризначте INT_MIN для максимальна_сума і від нуля до поточна_сумаТут INT_MIN представляє мінімальне ціле числове значення.

Крок 2) При індексі 0 значення дорівнює 4. Отже, поточна_сума = 0 + 4 = 4. Оскільки поточна_сума більше, ніж максимальна_сума, максимальна_сума стає 4.

Крок 3) При індексі 1 значення дорівнює -2. Отже, поточна_сума = 4 + (-2) = 2.

Цього разу поточна_сума менше, ніж максимальна_сумаВ результаті, значення максимальна_сума не оновлюється.

Крок 4) Наступне значення — 1. Додаючи його до поточна_сума дає 3. Оскільки максимальна_сума (4) все ще більше, ніж поточна_сума, максимальна_сума не оновлюється.

Крок 5) Для індексу 3 значення дорівнює 3. Збільшення поточна_сума на 3 дає поточна_сума = 6.

В цьому випадку, максимальна_сума менше, ніж поточна_сума, так максимальна_сума оновлюється значенням поточна_сума.

Крок 6) Для останнього елемента масиву ми маємо -1. Додаючи його до поточна_сума дає 5, що менше, ніж максимальна_сума. Тому, максимальна_сума залишається 6.

Оскільки ми дійшли до кінця масиву, алгоритм тут завершується. Тепер, максимальна_сума містить максимальну суму, яка дорівнює 6. Підмасив має вигляд {4, -2, 1, 3}.

Псевдо Code для алгоритму Кадане

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element in array:
        add the element with current_sum
        if current_sum is greater than the maximum_sum
            then maximum_sum = current_sum
        if current_sum is less than the element
            then current_sum = element
    return the value of maximum_sum

C++ Реалізація алгоритму Кадане

#include <iostream>
using namespace std;
void kadane(int array[], int n) {
    int current_sum = 0;
    int max_sum = -1e9;
    // -1e9 means -1,000,000,000
    for (int i = 0; i < n; i++) {
        current_sum += array[i];
        if (max_sum < current_sum) {
            max_sum = current_sum;
        }
        if (current_sum < array[i]) {
            current_sum = array[i];
        }
    }
    cout << "largest sum is " << max_sum << endl;
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    kadane(array, sizeof(array) / sizeof(array[0]));
}

вихід:

largest sum is 12

Python Реалізація алгоритму Кадане

def kadane(numbers):
    current_sum = 0
    max_sum = -1e9
    for i in range(len(numbers)):
        current_sum += numbers[i]
        if max_sum < current_sum:
            max_sum = current_sum
        if current_sum < numbers[i]:
            current_sum = numbers[i]
    print("largest sum is ", max_sum)

kadane([-10, 5, 1, 6, -9, 2, -7, 3, -5])

вихід:

largest sum is 12

Аналіз складності для суміжного підмасиву з найбільшою сумою

Простий підхід використовує два цикли для обчислення кожної можливої ​​суми підмасиву та знаходження найбільшої з них. Це підхід методом перебору; кожен цикл виконується до кінця масив, даючи O(N²) часу.

Алгоритм Кадане використовує лише один цикл, що дає O(N) часу та O(1) додаткового простору. На масиві зі 100 елементів простий підхід виконує 100 × 100 = 10 000 операцій, тоді як підхід Кадане виконує лише 100 — значне прискорення для великих вхідних даних.

Поширені запитання