Алгоритм Каденса: суміжний підмасив з найбільшою сумою
Сара Чен
Який найбільший суміжний підмасив?
Підмасив — це безперервна частина масиву. Це може бути один елемент масиву або частина масиву. Суміжний підмасив із найбільшою сумою означає підмасив із максимальним сумарним значенням.
Наприклад, масив має вигляд {-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} = 11 є максимальною сумою в усіх можливих комбінаціях підмасиву вищевказаного масиву. Отже, для наведеного вище масиву максимальний підмасив становить {5,1,6}.
Алгоритм Каденса: суміжний підмасив з найбільшою сумою
Простий підхід до вирішення суміжного підмасиву з найбільшою сумою
Простий спосіб розв’язати цю задачу — використати два цикли, щоб знайти всі підмасиви, обчислити суму, а потім знайти її максимальне значення.
Ось блок-схема для простого підходу до пошуку суміжного підмасиву з найбільшою сумою. Це підхід грубої сили, оскільки ми переглядаємо всі можливі підмасиви.
Ось прості кроки для цього.
Крок 1) Ініціалізуйте max_sum мінімальним цілим значенням і призначте змінним «begin» і «end» нуль.
Крок 2) Нехай i та j є індексом масиву, де «j» більше, ніж дорівнює «i». Він представляє початковий індекс підмасиву, а «j» представляє кінцевий індекс підмасиву.
Крок 3) «Current_sum» буде містити суму підмасиву. Після обчислення поточної суми перевірте, чи поточна_сума більша за максимальну_суму.
Крок 4) Якщо current_sum більше, тоді замініть max_sum на поточну суму.
Крок 5) Перевірте, чи досягає «j» кінця масиву чи ні. Якщо «j» досягає кінця масиву, тоді збільште «i» та змініть значення current_sum на 0.
Крок 6) Виконайте всі ці кроки, поки «i» не досягне кінця масиву.
Крок 7) Наприкінці цих двох циклів max_sum буде містити найбільшу суму підмасиву.
Псевдокод для простого підходу
function maximumSubarraySum():
input: array
for all possible subArray from array:
calculate sum of each sub array
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) Створіть дві змінні, current_sum і max_sum.
«Current_sum» зберігатиме значення максимальної суми, яка закінчується певним індексом масиву, тоді як «max_sum» зберігатиме максимальне значення підсумовування на даний момент.
Крок 2) Ми додамо значення з current_sum для кожного елемента масиву. Тоді ми перевіримо дві умови нижче:
- Якщо current_sum менше поточного елемента, поточним елементом буде значення current_sum.
- Якщо max_sum менше поточної_суми, то max_sum буде поточною_сумою.
Крок 3) Виконуючи попередній крок для всього масиву, ми матимемо суміжний підмасив з найбільшою сумою в змінній “max_sum”.
Приклад алгоритму Кадане
Ми продемонструємо алгоритм Каданеса з невеликим масивом і обговоримо кожен крок пошуку суміжного підмасиву з найбільшою сумою.
Припустімо, що даний масив виглядає так:
Ось кроки алгоритму Кадане:
Крок 1) Створіть дві змінні, current_sum і max_sum. Призначте INT_MIN для max_sum і нуль для current_sum. (Тут INT_MIN означає мінімальне ціле число).
Крок 2) При індексі 0 значення дорівнює 4. Отже, current_sum = 0 + 4 або 4. Тут current_sum більше, ніж max_sum, max_sum буде 4.
Крок 3) При індексі 1 значення дорівнює -2. Отже, поточна_сума = 4 + (-2) або 2.
Цього разу поточна_сума менша за максимальну_суму. У результаті значення max_sum не буде оновлено.
Крок 4) Наступне значення — 1. Якщо ми додамо це до поточної_суми, тоді поточна_сума буде 3. Проте максимальна_сума більша за поточну_суму. Отже, max_sum не буде оновлено.
Крок 5) При індексі 3 значення дорівнює трьом. Ми оновимо значення, збільшивши current_sum на 3. Отже, current_sum буде 6.
У цьому випадку max_sum менший за current_sum. Отже, max_sum буде оновлено на значення current_sum.
Крок 6) Для останнього елемента масиву ми маємо -1. Якщо ми додамо це до поточної_суми, поточна_сума буде 5, що менше, ніж максимальна_сума. Отже, max_sum залишиться 6.
Коли ми досягли кінця масиву, тут алгоритм закінчується. Тепер «max_sum» містить підмасив максимальної суми. Що дорівнює 5. Підмасив дорівнює {4,-2,1,3}.
Псевдокод для алгоритму Кадане
function KadaneAlgorithm():
input: array
maximum_sum, current_sum = 0
for each elements 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 -10000000
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
Аналіз складності для суміжного підмасиву з найбільшою сумою
Простий підхід використовує два цикли. Цей метод обчислює всі можливі суми підмасивів, щоб знайти найбільшу. Це підхід грубої сили. Кожна петля виконується до кінця масив.
Якщо масив має загальну кількість N елементів, то за допомогою двох петель ми пройдемо через N2 елементів. Як наслідок, часова складність простого підходу для знаходження суміжного підмасиву з найбільшою сумою буде O(N2). Тут «O» означає функцію складності.
З іншого боку, алгоритм Кадане — це метод динамічного програмування для знаходження максимального підмасиву безперервної суми. Якщо ви наслідуєте приклад або код, то побачите, що ми використовуємо лише один цикл.
У результаті, якщо вхідний масив має розмір N, то часова складність алгоритму Кадане буде O(N). Це швидше, ніж простий підхід. Наприклад, масив із 100 елементів. Простий підхід займе 100*100 або 10,000 100 процесорного часу. Але алгоритм Kadane займе лише XNUMX процесорного часу.
