Maksimālā apakšmasīva problēma ir tāda pati kā maksimālā slāņa problēma. Šajā apmācībā ir apskatīta problēma ar kodēšanu C++. Jautājums ir: kāda ir jebkuras iespējamās secīgo skaitļu virknes maksimālā summa masīvā? Tas var nozīmēt visu masīvu. Šo problēmu un tās risinājumu jebkurā valodā sauc par maksimālā apakšmasīva problēmu. Masīvā var būt iespējami negatīvi skaitļi.
Risinājumam ir jābūt efektīvam. Tam jābūt ar ātrāko laika sarežģītību. Šobrīd ātrākais risinājuma algoritms zinātnieku aprindās ir pazīstams kā Kadane's Algorithm. Šajā rakstā ir izskaidrots Kadane algoritms ar C++.
Datu piemēri
Apsveriet šādu vektoru (masīvu):
vektors < starpt > A = { 5 ,- 7 , 3 , 5 ,- divi , 4 ,- 1 } ;
Šķēle (apakšmasīvs) ar maksimālo summu ir secība {3, 5, -2, 4}, kas dod summu 10. Neviena cita iespējamā secība, pat viss masīvs, nedos summu līdz vērtība 10. Viss masīvs dod summu 7, kas nav maksimālā summa.
Apsveriet šādu vektoru:
vektors < starpt > B = { - divi , 1 ,- 3 , 4 ,- 1 , divi , 1 ,- 5 , 4 } ;
Šķēle (apakšmasīvs) ar maksimālo summu ir secība {4, −1, 2, 1}, kas dod summu 6. Ņemiet vērā, ka apakšmasīvā var būt negatīvi skaitļi, lai iegūtu maksimālo summu.
Apsveriet šādu vektoru:
vektors < starpt > C = { 3 , divi ,- 6 , 4 , 0 } ;
Šķēle (apakšmasīvs) ar maksimālo summu ir secība {3, 2}, kas dod summu 5.
Apsveriet šādu vektoru:
vektors < starpt > D = { 3 , divi , 6 ,- 1 , 4 , 5 ,- 1 , divi } ;
Apakšmasīvs ar maksimālo summu ir secība {3, 2, 6, -1, 4, 5, -1, 2}, kas dod summu 20. Tas ir viss masīvs.
Apsveriet šādu vektoru:
vektors < starpt > E = { 5 , 7 ,- 4 ,- 10 ,- 6 , 6 , 5 , 10 ,- 5 , piecpadsmit , 4 ,- 8 ,- piecpadsmit ,- 22 } ;
Šeit ir divi apakšmasīvi ar maksimālajām summām. Lielāka summa ir tā, kas tiek uzskatīta par maksimālās apakšmasīva problēmas risinājumu (atbildi). Apakšmasīvi ir: {5, 7} ar summu 12 un {6, 5, 10, -5, 15, 4} ar summu 35. Protams, šķēle ar summu 35 ir atbilde.
Apsveriet šādu vektoru:
vektors < starpt > F = { - 4 , 10 , piecpadsmit , 9 ,- 5 ,- divdesmit ,- 3 ,- 12 ,- 3 , 4 , 6 , 3 , divi , 8 , 3 ,- 5 ,- divi } ;
Ir divi apakšmasīvi ar maksimālajām summām. Lielāka summa ir tā, kas tiek uzskatīta par maksimālās apakšmasīva problēmas risinājumu. Apakšmasīvi ir: {10, 15, 9} ar summu 34 un {4, 6, 3, 2, 8, 3} ar summu 26. Protams, šķēle ar summu 34 ir atbilde, jo problēma ir meklēt apakšmasīvu ar lielāko summu, nevis apakšmasīvu ar lielāku summu.
Kadanes algoritma izstrāde
Informācija šajā apmācības sadaļā nav oriģinālais Kadanes darbs. Tas ir paša autora veids, kā iemācīt Kadanes algoritmu. Viens no iepriekš minētajiem vektoriem ar tā tekošajām summām ir šajā tabulā:
| Dati | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | piecpadsmit | 4 | -8 | - piecpadsmit | -22 |
| Skrējiena Total | 5 | 12 | 8 | - divi | -8 | - divi | 3 | 13 | 8 | 23 | 27 | divdesmitviens | 16 | -6 |
| rādītājs | 0 | 1 | divi | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | vienpadsmit | 12 | 13 |
Indeksa kopējā vērtība ir visu iepriekšējo vērtību summa, ieskaitot indeksa vērtību. Šeit ir divas secības ar maksimālajām summām. Tie ir {5, 7}, kas dod summu 12, un {6, 5, 10, -5, 15, 4}, kas dod summu 35. Secība, kas dod summu 35, ir vēlamā. .
Ņemiet vērā, ka tekošajām summām ir divi maksimumi, kas ir vērtības — 12 un 27. Šīs virsotnes atbilst abu secību pēdējiem indeksiem.
Tātad, Kadane algoritma ideja ir veikt darbības kopējo summu, salīdzinot maksimālās summas, kad tās tiek konstatētas, virzoties no kreisās puses uz labo dotajā masīvā.
Vēl viens vektors no augšas ar tā tekošajām summām ir šajā tabulā:
Ir divas secības ar maksimālo summu. Tie ir {10, 15, 9}, kas dod summu 34; un {4, 6, 3, 2, 8, 3}, kas dod summu 26. Secība, kas dod summu 34, ir vēlama.
Ievērojiet, ka tekošajām summām ir divi maksimumi, kas ir vērtības — 30 un 13. Šie maksimumi atbilst abu secību pēdējiem indeksiem.
Atkal, Kadane algoritma ideja ir veikt darbības kopsummu, vienlaikus salīdzinot maksimālās summas, kad tās tiek konstatētas, virzoties no kreisās puses uz labo dotajā masīvā.
Kods ar Kadane algoritmu C++ valodā
Šajā raksta sadaļā norādītais kods ne vienmēr ir tas, ko izmantoja Kadane. Tomēr tas ir pēc viņa algoritma. Programma, tāpat kā daudzas citas C++ programmas, sāksies ar:
#include#iekļaut
izmantojot namespace std;
Ir iekļauta iostream bibliotēka, kas ir atbildīga par ievadi un izvadi. Tiek izmantota standarta nosaukumvieta.
Kadane algoritma ideja ir iegūt kopējo summu, vienlaikus salīdzinot maksimālās summas, kad tās tiek konstatētas, virzoties no kreisās uz labo dotajā masīvā. Algoritma funkcija ir:
int maxSunArray ( vektors < starpt > & A ) {int N = A.izmērs ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
priekš ( starpt i = 1 ; i < N; i++ ) {
int tempRunTotal = runTotal + A [ i ] ; // varētu būt mazāks par A [ i ]
ja ( A [ i ] > tempRunTotal )
runTotal = A [ i ] ; // iekšā lietu A [ i ] ir lielāks par skriešanas kopsummu
cits
runTotal = tempRunTotal;
ja ( runTotal > maxAmount ) // salīdzinot visas maksimālās summas
maxSum = runTotal;
}
atgriezties maxAmount;
}
Tiek noteikts dotā masīva (vektora) izmērs, N. Mainīgais, maxSum, ir viena no iespējamajām maksimālajām summām. Masīvam ir vismaz viena maksimālā summa. Mainīgais runTotal apzīmē katra indeksa kopējo kopējo vērtību. Tie abi ir inicializēti ar pirmo masīva vērtību. Šajā algoritmā, ja nākamā vērtība masīvā ir lielāka par kopējo kopējo vērtību, šī nākamā vērtība kļūs par jauno kopējo vērtību.
Ir viena galvenā for-cilpa. Skenēšana sākas no 1, nevis no nulles, jo tiek inicializēti mainīgie, maxSum un runTotal uz A[0], kas ir dotā masīva pirmais elements.
For-cilpā pirmais priekšraksts nosaka pagaidu darbības kopsummu, pievienojot pašreizējo vērtību visu iepriekšējo vērtību uzkrātajai summai.
Tālāk ir if/else konstrukcija. Ja pašreizējā vērtība viena pati ir lielāka par pašreizējo kopējo vērtību, šī viena vērtība kļūst par kopējo vērtību. Tas ir ērti, jo īpaši, ja visas vērtības dotajā masīvā ir negatīvas. Šajā gadījumā augstākā negatīvā vērtība vien kļūs par maksimālo vērtību (atbildi). Ja pašreizējā vērtība viena pati nav lielāka par pagaidu kopējo kopējo vērtību, tad pašreizējā kopējā vērtība kļūst par iepriekšējo kopējo vērtību plus pašreizējā vērtība — šī ir if/else konstrukcijas else-daļa.
Pēdējais koda segments for-cilpā izvēlas starp jebkuru iepriekšējo maksimālo summu iepriekšējai secībai (apakšmasīvai) un jebkuru pašreizējo maksimālo summu pašreizējai secībai. Tāpēc tiek izvēlēta augstākā vērtība. Var būt vairāk nekā viena maksimālā apakšmasīva summa. Ņemiet vērā, ka kopsumma pieaugs un samazināsies, jo masīvs tiek skenēts no kreisās puses uz labo. Tas krīt, jo tas atbilst negatīvām vērtībām.
Galīgā izvēlētā maksimālā apakšmasīva summa tiek atgriezta pēc for-cilpas.
Piemērotas C++ galvenās funkcijas saturs Kadane algoritma funkcijai ir:
vektors < starpt > A = { 5 ,- 7 , 3 , 5 ,- divi , 4 ,- 1 } ; // { 3 , 5 ,- divi , 4 } - > 10int ret1 = maxSunArray ( A ) ;
cout << ret1 << endl;
vektors < starpt > B = { - divi , 1 ,- 3 , 4 ,- 1 , divi , 1 ,- 5 , 4 } ; // { 4 , − 1 , divi , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << endl;
vektors < starpt > C = { 3 , divi ,- 6 , 4 , 0 } ; // { 3 , divi } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << endl;
vektors < starpt > D = { 3 , divi , 6 ,- 1 , 4 , 5 ,- 1 , divi } ; // { 3 , divi , 6 ,- 1 , 4 , 5 ,- 1 , divi } - > 5
int ret4 = maxSunArray ( D ) ;
cout << tīkls4 << endl;
vektors < starpt > E = { 5 , 7 ,- 4 ,- 10 ,- 6 , 6 , 5 , 10 ,- 5 , piecpadsmit , 4 ,- 8 ,- piecpadsmit ,- 22 } ; // { 6 , 5 , 10 ,- 5 , piecpadsmit , 4 } - > 35
int ret5 = maxSunArray ( UN ) ;
cout << ret5 << endl;
vektors < starpt > F = { - 4 , 10 , piecpadsmit , 9 ,- 5 ,- divdesmit ,- 3 ,- 12 ,- 3 , 4 , 6 , 3 , divi , 8 , 3 ,- 5 ,- divi } ; // { 10 , piecpadsmit , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << pa labi 6 << endl;
Tādējādi izvade būs:
10
6
5
divdesmit
35
3. 4
Katra rinda atbilde šeit atbilst noteiktam masīvam, secībā.
Secinājums
Kadane algoritma laika sarežģītība ir O(n), kur n ir elementu skaits dotajā masīvā. Šī laika sarežģītība ir ātrākā maksimālā apakšmasīva problēmai. Ir arī citi algoritmi, kas darbojas lēnāk. Kadanes algoritma ideja ir veikt darbības kopsummu, vienlaikus salīdzinot maksimālās summas, kad tās tiek konstatētas, virzoties no kreisās uz labo dotajā masīvā. Ja pašreizējā vērtība pati par sevi ir lielāka par pašreizējo kopējo vērtību, šī viena vērtība kļūst par jauno kopējo vērtību. Pretējā gadījumā jaunā kopējā kopsumma ir iepriekšējā kopsumma plus pašreizējais elements, kā paredzēts, kad tiek skenēts dotais masīvs.
Var būt vairāk nekā viena maksimālā summa dažādiem iespējamiem apakšmasīviem. Tiek izvēlēta lielākā maksimālā summa visiem iespējamajiem apakšmasīviem.
Kādi ir ierobežojošie indeksi izvēlētās maksimālās summas diapazonam? – Tā ir diskusija kādu citu reizi!
Chrys