Најдиректнији могући начин да се задатак реши је да се израчуна збир сваког сегмента. Збир сваког сегмента можемо израчунавати засебно (у петљи или библиотечком функцијом), међутим, ефикасније решење добијамо ако сегменте набрајамо редом (угнежђеним петљама, где спољашња петља набраја редом леве, а унутрашња десне крајеве сегмената) и збир наредног сегмента израчунавамо инкрементално, на основу збира претходног сегмента. Та техника је објашњена у задатку Највећи збир префикса.
Сложеност. Ако збир сваког сегмента рачунамо независно, сабирањем његових елемената (било у петљи, било помоћу библиотечке функције), сложеност решења је \(O(n^3)\). Ако збирове сегмената рачунамо инкрементално, добијамо алгоритам сложености \(O(n^2)\). У оба случаја елементе учитавамо у низ и меморијска сложеност је \(O(n)\).
#include <iostream>
#include <vector>
using namespace std;
int maksZbirSegmenta(const vector<int>& a) {
int n = a.size();
int max = 0;
for (int i = 0; i < n; i++) {
int z = 0;
for (int j = i; j < n; j++) {
z += a[j];
if (z > max)
max = z;
}
}
return max;
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << maksZbirSegmenta(a) << endl;
return 0;
}Алгоритам заснован на провери свих сегмената се слободно може назвати тривијалним, јер се до њега долази прилично директно и веома једноставно му се и доказује коректност и анализира сложеност. Међутим, он је прилично неефикасан за решавање овог проблема, чак и када се збирови рачунају инкрементално. Значајно унапређење можемо добити када приметимо да велики број сегмената уопште не морамо да обрађујемо, јер из неких других разлога знамо да њихов збир не може бити максималан.
Посматрајмо низ -2 3 2 -3 -3 4 -2 5 -8 3 и збирове свих његових непразних сегмената.
-2 1 3 0 -3 1 -1 4 -4 -1 3 5 2 -1 3 1 6 -2 1 2 -1 -4 0 -2 3 -5 -2 -3 -6 -2 -4 1 -7 -4 -3 1 -1 4 -4 -1 4 2 7 -1 2 -2 3 -5 -2 5 -3 0 -8 -5 3
Размотримо било који низ који почиње негативним бројем. Ниједан сегмент који почиње од тог броја, не може бити сегмент максималног збира, пошто се изостављањам првог броја добија већи збир. Ово својство је и општије. Уколико низ почиње префиксом негативног збира, из истог разлога, ниједан сегмент чији је он префикс не може бити сегмент максималног збира. Отуд, при инкременталном проширивању интервала удесно, чим се установи да је текући збир негативан, могуће је прекинути даље проширивање.
На пример, чим видимо да је први елемент првог сегмента -2, можемо прекинути даљу обраду елемената прве врсте, јер ће сви елементи друге врсте сигурно бити за два већи него одговарајући елементи прве врсте (3 је веће од 1, 5 је веће од 3, 2 је веће од 0 итд.).
Слично, када се приликом проширивања сегмента који почиње на позицији 1 (од елемента 3) дође до тога да је парцијални збир -1 (што се дешава када се израчуна збир \(3+2-3-3=-1\), можемо прекинути са обрадом даљих сегмената који почињу на тој позицији, јер смо сигурни да ће за сваки од њих касније већи бити онај који се добија изостављање префикса 3 2 -3 -3, чији је збир -1. Заиста од преосталих збирова 3 1 6 -2 1 у другој врсти за један су већи збирови 4 2 7 -1 2 у шестој врсти који су добијени изостављањем тог префикса. Обратимо пажњу на то да прекид унутрашње петље на овај начин узрокује да се максимална вредност у текућој врсти не мора уопште наћи. Петља која обрађује другу врсту ће бити прекинута чим се наиђе на збир -1, када је текућа вредност максимума 5 иако је максимум те врсте 6. Сигурни смо да ће у некој наредној врсти постојати већа вредност од те највеће (заиста, у шестој врсти се јавља 7), па нам налажење стварног максимума у текућој врсти уопште није неопходно.
Сложеност. Иако се на овај начин може прескочити разматрање неких сегмената, у најгорем случају сложеност није смањена. На пример, у случају да су елементи низа строго позитивни, збир никад не постаје негативан и сложеност након овог исецања је и даље квадратне сложености тј. \(O(n^2)\).
Ако су сви елементи позитивни, максималан збир бива нађен за \(i=0\) и \(j=n-1\). Након тога се, увећавањем индекса \(i\), збир смањује пошто се сваким скраћивањем сегмента слева изоставља неки позитиван број који доприноси збиру. И ово запажање се може уопштити. Не само што је непожељно скратити интервал слева за неки позитиван број, већ је непожељно скратити га за било који префикс чији је збир позитиван. Питање је докле такви префикси сежу? Бар до елемента чијим обухватањем добијамо први негативан префикс. Отуд сегмент максималног збира не може почињати ни на једној позицији између текуће почетне позиције и прве позиције на којој збир постаје негативан.
На пример, у наведеном примеру максимални сегмент не може почињати на позицији 2, јер се проширивањем налево и додавањем елемента 3 са позиције 1 добијају сигурно збирови који су већи за три. Дакле, сви елементи друге врсте (која одговара позицији 1 у низу) су за 3 већи од одговарајућих елемената треће врсте (која одговара позицији 2 у низу). Заиста, 5 је веће од 2, 2 од -1 итд. Слично, ти елементи су за 5 већи од одговарајућих елемената четврте врсте (која одговара позицији 3 у низу). Заиста, 2 је веће од -3, -1 од -6 итд. Они су за 2 већи од одговарајући елемената пете врсте (која одговара позицији 4 у низу). Заиста, -1 је веће од -3, -3 је веће од -5 итд. Зато те три врсте уопште нема потребе разматрати.
Захваљујући овом запажању, при завршетку обраде једне врсте и преласку на наредну, није неопходно увећавати променљиву \(i\) за један, већ је могуће наставити иза елемента чијим је укључивањем збир постао негативан.
Пошто се сваки елемент обрађује само једном, приликом имплементације није неопходно све елементе памтити у низу.
У наредном аплету можете видети како овај алгоритам функционише.
✖
Пример. Прикажимо рад алгоритма на примеру низа -2 3 2 -3 -3 -2 4 5 -8 3. У таблици попуњавамо вредности променљивих током обраде елемената низа.
i j max z a_j 0 0 0 0 0 -2 -2 1 1 0 1 3 3 3 2 5 5 2 3 5 2 -3 4 -1 -3 5 5 0 5 -2 -2 6 6 0 6 5 4 4 7 9 9 5 8 9 1 -8 9 9 4 3 10 11
Сложеност. Пошто обе променљиве пролазе кроз распон од \(0\) до \(n\) и крећу се само у једном смеру (вредност им се само повећава и никада не смањује), сложеност овог решења је линеарна тј. \(O(n)\). У приказаној имплементацији елементи се чувају у низу па је и меморијска сложеност линеарна тј. \(O(n)\), међутим, пошто се сваки елемент анализира само једном, за тим нема потребе и могуће је направити и имплементацију константне меморијске сложености.
#include <iostream>
#include <vector>
using namespace std;
int maksZbirSegmenta(const vector<int>& a) {
int n = a.size();
int max = 0;
int i = 0;
while (i < n) {
int z = 0;
int j;
for (j = i; j < n; j++) {
z += a[j];
if (z < 0)
break;
if (z > max)
max = z;
}
i = j + 1;
}
return max;
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << maksZbirSegmenta(a) << endl;
return 0;
}