Maksimalios dalies masyvo problema yra tokia pati kaip ir didžiausio masyvo problema. Šioje pamokoje aptariama C++ kodavimo problema. Kyla klausimas: kokia yra didžiausia bet kokios galimos iš eilės einančių skaičių sekos masyve suma? Tai gali reikšti visą masyvą. Ši problema ir jos sprendimas bet kuria kalba vadinama maksimalia pomasyvo problema. Masyve gali būti galimi neigiami skaičiai.
Sprendimas turi būti efektyvus. Jis turi turėti greičiausią laiko sudėtingumą. Iki šiol greičiausias sprendimo algoritmas mokslo bendruomenėje yra žinomas kaip Kadane's Algorithm. Šiame straipsnyje paaiškinamas Kadane algoritmas su C++.
Duomenų pavyzdžiai
Apsvarstykite šį vektorių (masyvą):
vektorius < tarpt > A = { 5 ,- 7 , 3 , 5 ,- du , 4 ,- 1 } ;
Pjūvis (pomasyvas) su didžiausia suma yra seka {3, 5, -2, 4}, kuri duoda sumą 10. Jokia kita galima seka, net ir visas masyvas, neduos sumos iki reikšmė 10. Visas masyvas duoda sumą 7, kuri nėra didžiausia suma.
Apsvarstykite šį vektorių:
vektorius < tarpt > B = { - du , 1 ,- 3 , 4 ,- 1 , du , 1 ,- 5 , 4 } ;
Pjūvis (submasyvas), kurio didžiausia suma, yra seka {4, −1, 2, 1}, kuri suteikia sumą 6. Atkreipkite dėmesį, kad masyve gali būti neigiami skaičiai, siekiant maksimalios sumos.
Apsvarstykite šį vektorių:
vektorius < tarpt > C = { 3 , du ,- 6 , 4 , 0 } ;
Pjūvis (pomasyvas) su didžiausia suma yra seka {3, 2}, kuri suteikia sumą 5.
Apsvarstykite šį vektorių:
vektorius < tarpt > D = { 3 , du , 6 ,- 1 , 4 , 5 ,- 1 , du } ;
Submasyvas su didžiausia suma yra seka {3, 2, 6, -1, 4, 5, -1, 2}, kuri duoda sumą 20. Tai visas masyvas.
Apsvarstykite šį vektorių:
vektorius < tarpt > E = { 5 , 7 ,- 4 ,- 10 ,- 6 , 6 , 5 , 10 ,- 5 , penkiolika , 4 ,- 8 ,- penkiolika ,- 22 } ;
Čia yra du masyvai su didžiausiomis sumomis. Didesnė suma yra ta, kuri laikoma didžiausios pomasyvo problemos sprendimu (atsakymu). Pomasyvai yra: {5, 7}, kurių suma yra 12, ir {6, 5, 10, -5, 15, 4}, kurių suma yra 35. Žinoma, pjūvis, kurio suma yra 35, yra atsakymas.
Apsvarstykite šį vektorių:
vektorius < tarpt > F = { - 4 , 10 , penkiolika , 9 ,- 5 ,- dvidešimt ,- 3 ,- 12 ,- 3 , 4 , 6 , 3 , du , 8 , 3 ,- 5 ,- du } ;
Yra du masyvai su maksimaliomis sumomis. Didesnė suma yra ta, kuri laikoma didžiausios pomasyvo problemos sprendimu. Pomasyvai yra: {10, 15, 9}, kurių suma yra 34, ir {4, 6, 3, 2, 8, 3}, kurių suma yra 26. Žinoma, pjūvis, kurio suma yra 34, yra atsakymas, nes problema yra ieškoti pomasyvo su didžiausia suma, o ne pomasyvo su didesne suma.
Kadane algoritmo kūrimas
Informacija šioje pamokos dalyje nėra originalus Kadane darbas. Tai paties autoriaus būdas išmokyti Kadane'o algoritmą. Vienas iš aukščiau pateiktų vektorių su jo einamosiomis sumomis yra šioje lentelėje:
| Duomenys | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | penkiolika | 4 | -8 | - penkiolika | -22 |
| Bėgimas Total | 5 | 12 | 8 | - du | -8 | - du | 3 | 13 | 8 | 23 | 27 | dvidešimt vienas | 16 | -6 |
| indeksas | 0 | 1 | du | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | vienuolika | 12 | 13 |
Vykdoma indekso suma yra visų ankstesnių reikšmių suma, įskaitant indekso vertes. Čia yra dvi sekos su didžiausiomis sumomis. Jie yra {5, 7}, kurie duoda sumą 12, ir {6, 5, 10, -5, 15, 4}, kuri duoda sumą 35. Seka, kuri duoda sumą 35, yra tai, ko norima .
Atkreipkite dėmesį, kad einamosioms sumoms yra dvi smailės, kurios yra vertės – 12 ir 27. Šios smailės atitinka paskutinius dviejų sekų indeksus.
Taigi, Kadane'o algoritmo idėja yra atlikti einamąją sumą, lyginant didžiausias sumas, kai jos susiduria, judant iš kairės į dešinę nurodytame masyve.
Kitas vektorius iš viršaus su jo einamosiomis sumomis yra šioje lentelėje:
Yra dvi sekos su didžiausiomis sumomis. Jie yra {10, 15, 9}, o tai duoda sumą 34; ir {4, 6, 3, 2, 8, 3}, kuri duoda sumą 26. Seka, kuri duoda sumą 34, yra tai, ko norima.
Atkreipkite dėmesį, kad einamosioms sumoms yra dvi smailės, kurios yra vertės, 30 ir 13. Šios smailės atitinka paskutinius dviejų sekų indeksus.
Vėlgi, Kadane'o algoritmo idėja yra atlikti einamąją sumą, lyginant didžiausias sumas, kai jos atsiranda, judant iš kairės į dešinę nurodytame masyve.
Kodas pagal Kadane'o algoritmą C++
Šiame straipsnio skyriuje pateiktas kodas nebūtinai yra tas, kurį naudojo Kadane. Tačiau tai yra jo algoritmas. Programa, kaip ir daugelis kitų C++ programų, prasidėtų taip:
#include#įtraukti
naudojant vardų sritį std;
Įtraukta iostream biblioteka, kuri yra atsakinga už įvestį ir išvestį. Naudojama standartinė vardų erdvė.
Kadane'o algoritmo idėja yra turėti einamąją sumą, lyginant didžiausias sumas, kai jos susiduria, judant iš kairės į dešinę nurodytame masyve. Algoritmo funkcija yra tokia:
int maxSunArray ( vektorius < tarpt > & A ) {int N = A.dydis ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
dėl ( tarpt i = 1 ; i < N; i++ ) {
int tempRunTotal = runTotal + A [ i ] ; // gali būti mažesnis nei A [ i ]
jeigu ( A [ i ] > tempRunTotal )
RunTotal = A [ i ] ; // in atveju A [ i ] yra didesnis nei bėgimo sumos
Kitas
runTotal = tempRunTotal;
jeigu ( RunTotal > maxAmount ) // lyginant visas maksimalias sumas
maxSum = runTotal;
}
grąžinti maxAmount;
}
Nustatomas duoto masyvo (vektoriaus) dydis, N. Kintamasis maxSum yra viena iš galimų maksimalių sumų. Masyve yra bent viena maksimali suma. Kintamasis, runTotal, reiškia einamąją sumą kiekviename indekse. Jie abu inicijuojami pirmąja masyvo reikšme. Pagal šį algoritmą, jei kita masyvo reikšmė yra didesnė už einamąją sumą, kita vertė taps nauja einamoji suma.
Yra viena pagrindinė for-kilpa. Nuskaitymas prasideda nuo 1, o ne nuo nulio, nes kintamieji maxSum ir runTotal inicijuojami iki A[0], kuris yra pirmasis nurodyto masyvo elementas.
For-kilpoje pirmasis sakinys nustato laikiną einamąją sumą, dabartinę vertę pridedant prie sukauptos visų ankstesnių reikšmių sumos.
Toliau yra if/else konstrukcija. Jei vien tik dabartinė vertė yra didesnė už einamąją sumą iki šiol, ta vienintelė vertė tampa einamąją sumą. Tai patogu, ypač jei visos nurodyto masyvo reikšmės yra neigiamos. Šiuo atveju vien didžiausia neigiama reikšmė taps didžiausia reikšme (atsakymu). Jei vien dabartinė vertė nėra didesnė už laikinąją einamąją sumą iki šiol, tada einamoji suma tampa ankstesne einamoji suma, pridėjus dabartinę vertę – tai yra if/else konstrukcijos kita dalis.
Paskutiniame ciklo kodo segmente pasirenkama bet kokia ankstesnė maksimali ankstesnės sekos (pomasyvo) suma ir bet kokia dabartinė maksimali dabartinės sekos suma. Todėl pasirenkama didesnė vertė. Gali būti daugiau nei viena didžiausia pomasyvo suma. Atkreipkite dėmesį, kad einamoji suma kiltų ir mažėtų, nes masyvas nuskaitomas iš kairės į dešinę. Jis krenta, kai atitinka neigiamas vertes.
Galutinė pasirinkta maksimali submasyvo suma grąžinama po ciklo for-ciklo.
Tinkamos C++ pagrindinės funkcijos, Kadane algoritmo funkcijos, turinys yra:
vektorius < tarpt > A = { 5 ,- 7 , 3 , 5 ,- du , 4 ,- 1 } ; // { 3 , 5 ,- du , 4 } - > 10int ret1 = maxSunArray ( A ) ;
cout << ret1 << endl;
vektorius < tarpt > B = { - du , 1 ,- 3 , 4 ,- 1 , du , 1 ,- 5 , 4 } ; // { 4 , − 1 , du , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << endl;
vektorius < tarpt > C = { 3 , du ,- 6 , 4 , 0 } ; // { 3 , du } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << endl;
vektorius < tarpt > D = { 3 , du , 6 ,- 1 , 4 , 5 ,- 1 , du } ; // { 3 , du , 6 ,- 1 , 4 , 5 ,- 1 , du } - > 5
int ret4 = maxSunArray ( D ) ;
cout << tinklas4 << endl;
vektorius < tarpt > E = { 5 , 7 ,- 4 ,- 10 ,- 6 , 6 , 5 , 10 ,- 5 , penkiolika , 4 ,- 8 ,- penkiolika ,- 22 } ; // { 6 , 5 , 10 ,- 5 , penkiolika , 4 } - > 35
int ret5 = maxSunArray ( IR ) ;
cout << ret5 << endl;
vektorius < tarpt > F = { - 4 , 10 , penkiolika , 9 ,- 5 ,- dvidešimt ,- 3 ,- 12 ,- 3 , 4 , 6 , 3 , du , 8 , 3 ,- 5 ,- du } ; // { 10 , penkiolika , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << dešinė 6 << endl;
Tokiu atveju išvestis bus tokia:
10
6
5
dvidešimt
35
3. 4
Kiekvienos eilutės atsakymas čia atitinka tam tikrą masyvą, eilės tvarka.
Išvada
Kadane'o algoritmo laiko sudėtingumas yra O(n), kur n yra elementų skaičius duotame masyve. Šis laiko sudėtingumas yra greičiausias didžiausios pomasyvo problemos atveju. Yra ir kitų lėtesnių algoritmų. Kadane algoritmo idėja yra atlikti einamąją sumą, lyginant didžiausias sumas, kai jos susiduria, judant iš kairės į dešinę nurodytame masyve. Jei vien dabartinė vertė yra didesnė nei iki šiol einamoji bendra vertė, ta vienintelė vertė tampa nauja einamoji suma. Kitu atveju nauja einamoji suma yra ankstesnė einamoji suma ir dabartinis elementas, kaip numatyta, kai nuskaitomas nurodytas masyvas.
Skirtingiems galimiems pomasyviams gali būti daugiau nei viena maksimali suma. Parenkama didžiausia didžiausia visų galimų pomasyvių suma.
Kokie yra pasirinktos maksimalios sumos diapazono ribojantys indeksai? – Tai bus diskusija kitam kartui!
Chrys